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 *b*^{2} 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 *k _{i}*‘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 *p _{i}*. Thus, for each

*i*, we can find an integer

*x*such that:

_{i} for *i* = 1, 2, 3, …

For each *i*, let and solve for *y _{i}* : the solution is unique since

*p*is odd. Now we have

_{i}.

And so is a multiple of *p _{i}* for each

*i*. Now given

*n*, we pick

*i*= 1, 2, …,

*n*. Since the

*p*‘s are distinct primes, by Chinese Remainder Theorem, there exists

_{i}*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 *p*_{1}, *p*_{2}, …, *p _{n}*. 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 4*mn* – *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 4*k*^{2} + 1 can never have a factor which is 3 modulo 4. Or, equivalently, all factors of 4*k*^{2} + 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 *n*^{2} + 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.