Maths Olympiad Prep

Library / /55 of 520

Number theory Difficulty 5.4 AIME, harder Find the answer

3. Use Theorem 2 to determine:
(i) whether -8 is a quadratic residue modulo 53;
(ii) whether 8 is a quadratic residue modulo 67.

A number or a short expression. Spacing and $ signs are ignored.

Solution

3. (i) (−8)26≡1113≡11⋅156≡11⋅133≡−16⋅10≡−1( mod 53),−8(-8)^{26} \equiv 11^{13} \equiv 11 \cdot 15^{6} \equiv 11 \cdot 13^{3} \equiv -16 \cdot 10 \equiv -1(\bmod 53), -8 is not a quadratic residue modulo 53; (ii) 833≡8⋅(3)16≡8⋅144≡8⋅52≡−1( mod 67),88^{33} \equiv 8 \cdot (3)^{16} \equiv 8 \cdot 14^{4} \equiv 8 \cdot 5^{2} \equiv -1(\bmod 67), 8 is not a quadratic residue modulo 67.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.