3.I.1H

Number Theory
Part II, 2006

Let N=p1p2prN=p_{1} p_{2} \ldots p_{r} be a product of distinct primes, and let λ(N)\lambda(N) be the least common multiple of p11,p21,,pr1p_{1}-1, p_{2}-1, \ldots, p_{r}-1. Prove that

aλ(N)1modN when (a,N)=1.a^{\lambda(N)} \equiv 1 \bmod N \quad \text { when } \quad(a, N)=1 .

Now take N=7×13×19N=7 \times 13 \times 19, and prove that

aN11modN when (a,N)=1.a^{N-1} \equiv 1 \bmod N \quad \text { when } \quad(a, N)=1 .