Competition problem — Number theory

Library / /141 of 520

Number theory Difficulty 5.8 AIME, harder Prove it

15. Let $q=4^{n}+1$ . Prove: $q$ is a prime if and only if
$3^{(q-1) / 2} \equiv-1(\bmod q)$

Solution

15. Necessity. Let $q$ be a prime. If the conclusion does not hold, then $\left(\frac{3}{q}\right)=1$ , which implies $q \equiv \pm 1$ $(\bmod 12)$ , a contradiction. Sufficiency. Let the smallest $h$ such that $3^{h} \equiv 1(\bmod q)$ be $h_{0} . h_{0} \mid q-1=2^{2 n}$ , and from $3^{2^{2 n-1}} \not \equiv 1(\bmod q)$ we get $h_{0}=q-1$ , so $q$ is a prime.

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.