Lecture 3: Lift That Exponent December 13
Lecturer: Shourya Pandey Scribe: Shourya Pandey The Lemma
Definition: For an integer x and a prime p, vp(x) denotes the higher power of the prime p dividing
x. We define vp(0) = ∞ for all primes p.
Lift The Exponent Lemma: Let n be a positive integer and let p = 2 be a prime. Suppose x
and y are integers such that neither x nor y is divisible by p, but p | x − y. Then
vp(xn − yn) = vp(x − y) + vp(n)
What about the case of p = 2? Let n be a positive even integer and let x, y be odd integers. Then
vp(xn − yn) = vp(x − y) + vp(x + y) + vp(n) − 1
Also, if 4 | x − y then for any positive integer n, we have
vp(xn − yn) = vp(x − y) + vp(n)
The theorem is simple enough, so let’s tackle some questions right away! 1 Easier Problems
Question 1. Let a, n be two positive integers, and let p be an odd prime such that ap ≡ 1 (mod pn) Prove that a ≡ 1 (mod pn−1) Is the above true if p = 2?
Question 2. Let p be a prime and let a, n be positive integers. Show that if an = 2p + 3p then n = 1.
Question 3. Find all positive integral solutions to (n − 1)! + 1 = nm Question 4. Evaluate v 19911992 1991(1990 + 199219911990). 1 2 Medium Problems
Question 5. Let a, b be distinct reals such that
a − b, a2 − b2, a3 − b3, · · ·
are integers. Show that a and b are integers.
Question 6. Find all positive integers n for which 2n + 1 n2 is a positive integer.
Question 7. Does there exist a positive integer n such that n has exactly 2000 prime divisors, and n | 2n + 1?
Question 8. Let n > 1 be a positive integer. Show that the sequence (ak)k∈N defined as ⌊ nk ⌋ ak = k
has infinitely many odd natural numbers. 3 Harder Problems
Question 9. Find all triples (x, y, p) consisting of two positive integers x and y, and a prime p,
such that both xp−1 + y and yp−1 + x are powers of p.
Question 10. Find all triples (a, b, c) of positive integers for which ab − c, bc − a, ca − b are all powers of 2.
Question 11. Let a > b > 1 be positive integers, and let b be odd. Let n be a positive inte-
ger such that bn | an − 1. Show that n · ab ≥ 3n.
Question 12. This exercise aims to prove that the group Z∗ is cyclic for all odd primes p and pn
natural numbers n, assuming Z∗ is cyclic. p
1. Make sure you can recall the definitions of Zm, Z∗ , primitive roots (or generators), and m cyclic groups. 2
2. Assume you know there exists an element g such that 1, g, g2, · · · , gp−2 are all distinct mod-
ulo p. Such a g is called a primitive root (or a generator) modulo p. Then, how many
1 ≤ i ≤ p − 1 exist such that gi is also a generator? Note that for gi to be a generator, it is
necessary and sufficient for 1, gi, g2i, · · · , g(p−2)i to be distinct modulo p.
3. The answer to the previous question is ϕ(p − 1) = ϕ(ϕ(p)). Now, we try to find a generator
modulo p2. Let g be a generator modulo p. Let h be the order of p modulo p2. Prove that
either h = p − 1 or h = p(p − 1).
4. Let g be a generator modulo p, where 0 < g < p. Then note that each of the numbers
g, g + p, g + 2p, · · · , g + (p − 1)p will be generators modulo p as well. Prove that gp−1, (g +
p)p−1, · · · , (g + (p − 1)p)p−1 are all distinct modulo p2.
5. Conclude from the previous exercise that among the numbers g, g+p, g+2p, · · · , g+(p−1)p,
exactly one of the numbers has order p−1 modulo p2, and the rest have order p(p−1) modulo p2.
6. Conclude that not only does there exist a number with order p(p − 1) modulo p2, but there
are, in fact, (p − 1) · ϕ(p − 1) = ϕ(ϕ(p2)) such numbers.
7. Let n ≥ 3 be a positive integer. Prove that if g is a generator modulo pn, then it is a generator
modulo p2. Conversely, show that if g is a generator modulo p2, then it is a generator modulo
pn. This shows that pn has pn−2 · (p − 1) · ϕ(p − 1) = ϕ(ϕ(pn)) generators modulo pn. This is where you might use LTE.
Question 13. From the previous exercise, we got that the set of numbers coprime to pn form a
cyclic group, where p is an odd prime and n is a positive integer.
1. Prove that for any odd prime p and natural number n, the group Z∗2 is cyclic. ·pn
2. Prove that the groups Z∗2 and Z∗4 are cyclic.
3. Prove that for m > 1, the group Z∗ is cyclic if, and only if, m = 2, 4, pn, or 2 · pn, for some m
odd prime p and some natural number n. 3