Let p be an odd prime and g be a primitive root modulo p. Given any a which is not a multiple of p, we can write for some r. We mentioned at the end of the last section that a is a square if and only if r is even.
This can be illustrated by the following diagram for p = 11 (with the concrete example g = 2).
The highlighted circles represent the squares modulo 11. Why is not a square for odd s? Well, if it were congruent to b2 mod p, we write for some t. Then we have , and by cancellation, we obtain for some odd u. This is impossible since any u for which must be a multiple of .
Problem 1. (USAMO 2008, Q1) Prove that for each integer n, there are pairwise relatively prime integers , all greater than 1, such that is a product of two consecutive integers.
Plan of Attack. Instead of looking for these ki‘s, we look for the product of two consecutive integers, given by N(N+1). So our plan of attack is to find a suitable N, then compute P = N(N+1)+1 and attempt to split it as a product of many relatively prime numbers: the easiest way to do it is via prime powers. Just obtain an N such that has many distinct prime factors!
Now suppose we wish to solve for fixed prime p. Then multiplying by 4 and completing the square gives . Thus we’re looking for primes p for which -3 is a square mod p.
Proof. Pick infinitely many odd primes which are congruent to 1 mod 3. [ This is always possible since by Dirichlet’s theorem, we can pick infinitely many primes which are a mod b, whenever (a, b) = 1. ] From example 3 in the previous installation, we know that for all i, i.e. -3 is a square modulo pi. Thus, for each i, we can find an integer xi such that:
for i = 1, 2, 3, …
For each i, let and solve for yi : the solution is unique since pi is odd. Now we have
And so is a multiple of pi for each i. Now given n, we pick i = 1, 2, …, n. Since the pi‘s are distinct primes, by Chinese Remainder Theorem, there exists N such that:
for i = 1, 2, …, n.
For each i = 1, 2, …, n, we thus have . Hence, our has at least n distinct prime factors, namely p1, p2, …, pn. Then we can write as a product of n pairwise relatively prime integers, which completes our proof. ♦
Problem 2. (IMO 1984 shorlisted) Prove that if m, n are positive integers, then 4mn – m – n can not be a perfect square.
Proof. Suppose . Then multiplying by 4 on both sides and factoring:
If we turn the problem around, we just need to show that 4k2 + 1 can never have a factor which is 3 modulo 4. Or, equivalently, all factors of 4k2 + 1 must be 1 modulo 4. It clearly suffices to show that all prime factors are 1 modulo 4. To that end, let be a prime factor. Then . So -1 is a square modulo p. This can only hold for all primes which are 1 modulo 4. ♦
Problem 3. (IMO 1992 longlisted) Let a, b be integers. Prove that is never an integer.
Proof. Suppose we fix b and let . Then we need to show that the congruence
has no solution. Suppose, on the contrary, there is. Then b must be odd. So the above congruence is equivalent to solving for , i.e. we must show that 2 cannot be a square modulo N.
To do that, we need to show that N has a prime factor p such that 2 is not a square modulo p. Equivalently, that N has a prime factor p which is 3 or 5 modulo 8. But this is clearly true since and so not all its prime factors are ±1 mod 8, thus at least one prime factor is 3 or 5 modulo 8. ♦
More problems below. Some of them may be quite hard, but problems 4 to 6 should be manageable – you’ll probably have to think quite a bit though.
Problem 4. Find the number of solutions for , in the range 0 ≤ x < n, in each of the following cases:
- n = 7 × 11 × 17 × 31 × 41 × 97;
- n = 7 × 17 × 41 × 103.
Problem 5. Let p > 3 be a prime. By picking a primitive root modulo p, or otherwise, prove the following (all solutions are to be computed in the range 0 ≤ x < p):
- if p ≡ 1 (mod 3), then has exactly 3 solutions;
- if p ≡ 2 (mod 3), then has a unique solution.
Problem 6. Prove that if p is an odd prime, then the congruence has a solution if and only if p is 1 modulo 8.
Problem 7. (IMO 1998 shortlisted) Find all positive integers n such that there exists a positive integer m, satisfying
Problem 8. Prove that if m, n are odd positive integers greater than 1, then does not divide . [ Note: this is where the link between quadratic residues and multiplicative order comes in handy. ]
Problem 9. (IMO 2008 Q3) Prove that there are infinitely many positive integers n such that n2 + 1 has a prime factor which is greater than .
I have a problem, for Q7 and 8 it doesn’t seem to mention odd primes anywhere, and if i understand it correctly QR only works for odd squares. Help?
[Warning: spoilers for Q7 and Q8!]
– For Q7, we’re asking for n for which -9 is a square mod . For n odd, this is equivalent to saying -1 is a square mod . Hence -1 is a square modulo every prime factor of (!). What can we say about these prime factors? For n even, I’ll leave it to you.
– For Q8, here’s a small hint. Prove that has a prime factor which does not divide . By contradiction…
Ooh, that should help, i assume you meant -9 is a square modulo every prime factor of 2^n-1, not -1.