Maths Olympiad Prep

Library / /107 of 520

Number theory Difficulty 5.6 AIME, harder Prove it

7. If qq is a natural number, p=4q+1p=4q+1 is a prime, prove that qq must be a quadratic residue modulo pp.

Solution

7. Proof: Since p1(mod4)p \equiv 1(\bmod 4), -1 must be a quadratic residue modulo pp, i.e., there exists an integer x0x_{0} such that
x021(modp)x_{0}^{2} \equiv -1(\bmod p)

On the other hand, from p=4q+1p=4 q+1 we also have
4q1(modp)4 q \equiv -1(\bmod p)

Therefore,
x024q(modp)x_{0}^{2} \equiv 4 q(\bmod p)

Since 2p2 \nmid p, there must be a y0y_{0} such that 2y01(modp)2 y_{0} \equiv 1(\bmod p), thus
(x0y0)2q(2y0)2q(modp)\left(x_{0} y_{0}\right)^{2} \equiv q\left(2 y_{0}\right)^{2} \equiv q(\bmod p)

This is exactly what we need to prove.

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.