Research Space for Linear Algebra & Discrete Mathematics
2008-08-07
Euler's Theorem證明問題，老師請看一下
Let f be an Euler phi-function
consider the ring z(n), u(z(n)) is a multiplicative group given any [a] in u(z(n)), gcd(a,n)=1 。(u(z(n)))=f(n) =>[a]^(f(n))=[1] in u(z(n)) (為什麼???) =>a^(f(n)) =1 mod n
拿 a 去造一個 cyclic subgroup H of u(z(n)), =>。(a)=。(H), 也就是說 a^。(H)=1 by Lagrange's Theorem, 。(H)|。(u(z(n))) 令。(u(z(n))) = f(n) = k*。(H), for some k => a^f(n) = (a^。(H))^k = 1^k = 1
拿 a 去造一個 cyclic subgroup H of u(z(n)),
回覆刪除=>。(a)=。(H), 也就是說 a^。(H)=1
by Lagrange's Theorem, 。(H)|。(u(z(n)))
令。(u(z(n))) = f(n) = k*。(H), for some k
=> a^f(n) = (a^。(H))^k = 1^k = 1