 Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# 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.

(5 pont)

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 a2m 1 (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/2 1 (mod p).

If m/s is an odd integer then am (as)m/s -1 (mod p) és (-am)-m 1m 1 (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.

### Statistics:

 5 students sent a solution. 5 points: Nagy 235 János, Tomon István. 2 points: 3 students.

Problems in Mathematics of KöMaL, October 2008