Assuming-FLT-prove-Fermat-Euler-theorem-a-n-1-n-2-a-n-1-mod-n-

Question Number 111704 by Aina Samuel Temidayo last updated on 04/Sep/20

Assuming FLT, prove Fermat - Euler

theorem : (a, n) = 1, n ⩾ 2 \Rightarrow a^{\emptyset (n)} \equiv 1 (\mod

n)

Answered by Aina Samuel Temidayo last updated on 04/Sep/20

Assuming FLT

(a, n) = 1, n ⩾ 2 \Rightarrow a^{\emptyset (n)} \equiv 1 (\mod n)

If n is prime, then \emptyset (n) = n - 1 and

{Euler}^{'} s theorem says a^{n - 1} = 1 (\mod n),

which is {Fermat}^{'} s theorem .

Since n is prime, then all of the

numbers {1, \dots, n - 1} are relatively

prime to n .

\Rightarrow \emptyset (n) = n - 1

Proof :

Let \emptyset (n) = k, and let {a_{1}, a_{2}, \dots, a_{k}} be a

residue system \mod n .

I may assume that the a_{i}^{'} s lie in the

range {1, \dots, n - 1} as a reduced

residue system \mod n is a set of

numbers

a_{1}, a_{2}, a_{3}, \dots, a_{\emptyset (n)}

such that :

- if i \neq j, then a_{i} \neq a_{j} (\mod n) . That is,

the a^{'} s are distinct \mod n .

- For each i, (a_{i}, n) = 1 .

That is, all the a^{'} s are relatively prime

to n .

Since all a^{'} s are relatively prime to n,

then the assumption that the a_{i}^{'} s lie in

the range {1, \dots, n - 1} is correct .

Since (a, n) = 1, {{aa}_{1}, \dots, {aa}_{k}} is another

reduced residue system \mod n . Since

this is the same set of numbers \mod n

as the original system, the two

systems must have the same product

\mod n :

\Rightarrow ({aa}_{1}) ({aa}_{2}) \dots ({aa}_{k}) = a_{1} \dots a_{k} (\mod n)

\Rightarrow a^{k} (a_{1} \dots a_{k}) = a_{1} \dots a_{k} (\mod n)

Now each a_{i} is invertible \mod n, so

multiplying both sides by

a_{1}^{- 1} \dots a_{k}^{- 1}, we get

a^{k} = 1 (\mod n)

Recall that \emptyset (n) = k

\Rightarrow a^{ϕ (n)} = 1 (\mod n)

Hence, proved .

Commented by Aina Samuel Temidayo last updated on 05/Sep/20

Is this correct ?