Problem A. 462. (October 2008)
A. 462. Let p be an odd prime and let 1<a<p be an integer. Prove that p divides if and only if there exists an odd positive integer k for which ak is congruent to 1 modulo p.
Deadline expired on December 15, 2008.
Solution. Let r be the order of the residue a modulo p,
(a) If r is odd, then
(b) If r is even, r=2s, then as-1 (mod p).
Let . We will show that ST is not divisible by p.
If r|2m, then a2m1 (mod p), and . In all other cases
If m/s is an even integer then m is even, -am-1 mod p), and (-am)-m((-1)2)m/21 (mod p).
If m/s is an odd integer then am(as)m/s-1 (mod p) és (-am)-m1m1 (mod p).
As we have seen, we obtain nonzero residues only when s divides m, and this residue is -1in all such cases. Therefore,
Since , this is not 0.
5 students sent a solution. 5 points: Nagy 235 János, Tomon István. 2 points: 3 students.