Use lagranges theorem in the multiplicative group (z/nz) to prove eulers theorem: a (n) 1(mod n) for every integer a relatively prime to n, where is eulers phi functio
Answers
Answer:
Hope this helps you. Plz mark it Brainliest!! :D
Z/nZ is not a multiplicative group because of 0.
However, the units (i.e. the numbers that don't divide 0) do form a multiplicative group. The (multiplicative) group that you want is this group of units in Z/nZ. Often, this group of units is indicated with an asterisk:
(Z/nZ)* = the group of units in Z/nZ
The units are the elements that don't divide 0, which in the context of Z/nZ, means the numbers that are coprime (i.e. relatively prime) to n. This is precisely what the Euler phi function counts, so
| (Z/nZ)* | = φ(n).
Lagrange's Theorem says that in any group G (written multiplicatively) with identity 1, we have a ^ |G| = 1.
So in (Z/nZ)*, we have
for a in (Z/nZ)*, a^φ(n) = 1 (in (Z/nZ)*)
=> for a coprime to n, a^φ(n) ≡ 1 (mod n)