Numbers and Sets | Part IA, 2004

Prove Fermat's Theorem: if pp is prime and (x,p)=1(x, p)=1 then xp11(modp)x^{p-1} \equiv 1(\bmod p).

Let nn and xx be positive integers with (x,n)=1(x, n)=1. Show that if n=mpn=m p where pp is prime and (m,p)=1(m, p)=1, then

xn11(modp) if and only if xm11(modp)x^{n-1} \equiv 1 \quad(\bmod p) \quad \text { if and only if } \quad x^{m-1} \equiv 1 \quad(\bmod p)

Now assume that nn is a product of distinct primes. Show that xn11(modn)x^{n-1} \equiv 1(\bmod n) if and only if, for every prime divisor pp of nn,

x(n/p)11(modp).x^{(n / p)-1} \equiv 1 \quad(\bmod p) .

Deduce that if every prime divisor pp of nn satisfies (p1)(n1)(p-1) \mid(n-1), then for every xx with (x,n)=1(x, n)=1, the congruence

xn11(modn)x^{n-1} \equiv 1 \quad(\bmod n)


Typos? Please submit corrections to this page on GitHub.