Math, asked by ganeshgk1861, 1 year ago

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

Answered by Anonymous
0

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)

Similar questions