The Mad Hatter is quite upset. He had this conjecture that the prime q = 41 was

Question

The Mad Hatter is quite upset. He had this conjecture that the prime q = 41 was a quadratic residue for all primes p of the form p 3 (mod 8). The goal was to show this was in fact true for a wide range of primes q and surely there must be cryptographic utility in all of this? The March Hare had ruined it all by coming with a specific counterexample – after some work – but now that annoying Cheshire Cat was sniggering that there is an infinite number of counterexamples. Can you save the Hatter’s conjecture that there is only a finite number of counterexamples or is the Cat correct?

You should remember Gauss’ Law of Quadratic Reciprocity – if m, n are odd then there is a relationship between m being a quadratic residue modulo n and n being a quadratic residue modulo m.

Explanation / Answer

Modular Arithmetic. Recall that a b (mod m) means that a and b have the same remainder when you divide each by m. Equivalently, a b (mod m) means exactly that m divides a b. When we talk about a (mod m) by itself, we are referring to the remainder of a divided by m (the “least residue”). This is always between 0 and m 1, inclusive. Theorem: Inverses Mod m. Let a be an integer relatively prime to m. Then there exists an integer b for which ab 1 (mod m). The integer b is the (multiplicative) inverse of a modulo m. For instance, the inverse of 5 modulo 13 is 8 because 5 · 8 = 40 1 (mod 13). Exercise 0. Find the inverse of 7 (mod 11), and the inverse of 11 (mod 7). Explain why 12 could never have an inverse (mod 15); e.g., why could there never be an integer b with 12b 1 (mod 15)? If p is a prime number, then every integer in the range 1, 2, . . . , p1 has an inverse modulo p, because all of those integers are relatively prime to p. For instance, if p = 5 then the numbers 1,2,3,4 have inverses 1,3,2,4 (mod 5). Notice that the sequence 1,3,2,4 is a permutation of 1,2,3,4. In related reasoning, suppose we multiplied everything in the sequence 1, 2, 3, 4 by 2 and reduced modulo 5. We get 2, 4, 1, 3, another permutation of 1,2,3,4. When we multiply both sequences together, we get (2 · 1)(2 · 2)(2 · 3)(2 · 4) 1 · 2 · 3 · 4 (mod 5), because after all these are the same four numbers (in a different order). On the other hand this equation reads 24 · 4! 4! (mod 5). Since 4! is relatively prime to 5, we can cancel it from both sides to get 24 1 (mod 5). The generalization of this was proved in 1640 by Fermat

Fermat’s Theorem. Let p be prime and let a be relatively prime to p. Then ap1 1 (mod p). Quadratic Residues. Let m and n be integers. We say that n is a square mod m if the equation x2 n (mod m) has a solution in x. In other words, n is a square mod m if it is congruent to a perfect square mod m. We also say that n is a quadratic residue for m.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.