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 b2 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 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 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 pi. Thus, for each i, we can find an integer xi 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 yi : the solution is unique since pi 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 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:

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 p1, p2, …, pn. 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 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 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 n2 + 1 has a prime factor which is greater than 2n + \sqrt{2n}.

This entry was posted in Notes and tagged , , , . Bookmark the permalink.

3 Responses to Quadratic Residues – Part IV (Applications)

  1. Eugene Lee says:

    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:

      [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:

        Ooh, that should help, i assume you meant -9 is a square modulo every prime factor of 2^n-1, not -1.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s