Quadratic Residues – Part IV (Applications)

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 $a \equiv g^r \pmod p$ 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 $g^s \pmod p$ not a square for odd s? Well, if it were congruent to b² mod p, we write $b \equiv g^t \pmod p$ for some t. Then we have $g^s \equiv g^{2t} \pmod p$ , and by cancellation, we obtain $g^u \equiv 1 \pmod p$ for some odd u. This is impossible since any u for which $g^u \equiv 1 \pmod p$ must be a multiple of $ord_p(g) = p-1$ .

–

Problem 1. (USAMO 2008, Q1) Prove that for each integer n, there are pairwise relatively prime integers $k_1, k_2, \dots, k_n$ , all greater than 1, such that $k_1 k_2 \ldots k_n - 1$ 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 $N^2 + N + 1$ has many distinct prime factors!

Now suppose we wish to solve $N^2 + N + 1 \equiv 0 \pmod p$ for fixed prime p. Then multiplying by 4 and completing the square gives $(2N+1)^2 + 3 \equiv 0 \pmod p$ . Thus we’re looking for primes p for which -3 is a square mod p.

Proof. Pick infinitely many odd primes $p_1, p_2, p_3, \dots$ 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 $(\frac {-3} {p_i}) = +1$ for all i, i.e. -3 is a square modulo p_i. Thus, for each i, we can find an integer x_i such that:

$x_i^2 \equiv -3 \pmod {p_i}$ for i = 1, 2, 3, …

For each i, let $2y_i + 1 \equiv x_i \pmod {p_i}$ and solve for y_i : the solution is unique since p_i is odd. Now we have

$(2y_i + 1)^2 \equiv -3 \pmod {p_i} \implies 4(y_i^2 + y_i + 1) \equiv 0 \pmod {p_i}$ .

And so $y_i^2 + y_i + 1$ is a multiple of p_i for each i. Now given n, we pick i = 1, 2, …, n. Since the p_i‘s are distinct primes, by Chinese Remainder Theorem, there exists N such that:

$N \equiv y_i \pmod {p_i}$ for i = 1, 2, …, n.

For each i = 1, 2, …, n, we thus have $N^2 + N + 1 \equiv y_i^2 + y_i + 1 \equiv 0 \pmod {p_i}$ . Hence, our $N^2 + N + 1$ has at least n distinct prime factors, namely p₁, p₂, …, p_n. Then we can write $N^2 + N + 1$ 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 $4mn - m - n = k^2$ . Then multiplying by 4 on both sides and factoring:

$(4m-1)(4n-1) = 4k^2 + 1$ .

If we turn the problem around, we just need to show that 4k² + 1 can never have a factor which is 3 modulo 4. Or, equivalently, all factors of 4k² + 1 must be 1 modulo 4. It clearly suffices to show that all prime factors are 1 modulo 4. To that end, let $p | (4k^2+1)$ be a prime factor. Then $(2k)^2 \equiv -1 \pmod p$ . 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 $\frac {2a^2 - 1} {b^2 + 2}$ is never an integer.

Proof. Suppose we fix b and let $N = b^2+2$ . Then we need to show that the congruence

$2a^2 - 1 \equiv 0 \pmod N$

has no solution. Suppose, on the contrary, there is. Then b must be odd. So the above congruence is equivalent to solving for $4a^2 \equiv 2 \pmod N$ , 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 $b^2 + 2 \equiv 3 \pmod 8$ 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 $x^2 \equiv 2 \pmod n$ , 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 $x^3 \equiv 1 \pmod p$ has exactly 3 solutions;
if p ≡ 2 (mod 3), then $x^3 \equiv 1 \pmod p$ has a unique solution.

Problem 6. Prove that if p is an odd prime, then the congruence $x^4 \equiv -1 \pmod p$ 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

$(2^n - 1) | (m^2 + 9).$

Problem 8. Prove that if m, n are odd positive integers greater than 1, then $2^m - 1$ does not divide $3^n - 1$ . [ 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² + 1 has a prime factor which is greater than $2n + \sqrt{2n}$ .

3 Responses to Quadratic Residues – Part IV (Applications)

Eugene Lee says:

December 7, 2011 at 1:42 pm

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?

- limsup says:
  
  December 7, 2011 at 2:27 pm
  
  [Warning: spoilers for Q7 and Q8!]
  
  – For Q7, we’re asking for n for which -9 is a square mod $2^n-1$ . For n odd, this is equivalent to saying -1 is a square mod $2^n-1$ . Hence -1 is a square modulo every prime factor of $2^n-1$ (!). 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 $2^m - 1$ has a prime factor which does not divide $3^n - 1$ . By contradiction…
  
  - Eugene Lee says:
    
    December 8, 2011 at 5:59 am
    
    Ooh, that should help, i assume you meant -9 is a square modulo every prime factor of 2^n-1, not -1.