Register to reply

Question from the proof in euler's forumla

by lifom
Tags: euler, forumla, proof
Share this thread:
lifom
#1
Mar14-11, 08:11 PM
P: 14
Let b1,b2,...bn be the integers between 1 and m that are relative prime to m (including 1), and let B = b1*b2*...*bn be their product. The quantity B came up during the proof of euler formula. a^n = 1 (mod m), where n is number of integers between 1 and m that relative prime to m.

How can I show B=1 (mod m ) or B = -1(mod m)?
Phys.Org News Partner Science news on Phys.org
Law changed to allow 'unlocking' cellphones
Microsoft sues Samsung alleging contract breach
Best evidence yet for coronal heating theory detected by NASA sounding rocket
micromass
#2
Mar14-11, 08:18 PM
Mentor
micromass's Avatar
P: 18,099
Have you seen Wilson's theorem? This states that (p-1)!=-1 (mod p) for prime p.

Can you adjust the proof so that it also works in this case?
lifom
#3
Mar14-11, 09:18 PM
P: 14
Quote Quote by micromass View Post
Have you seen Wilson's theorem? This states that (p-1)!=-1 (mod p) for prime p.

Can you adjust the proof so that it also works in this case?
I have tried, but fail in the last step:
In Wilson's proof, the number satisfy a^2=1(mod p) -> (a-1)(a+1) = p*n. Since 0<=a<p
a= 1 or p-1 only. So for 2,3,...,p-2, I can group them into pairs without repeat such that the pair product = 1 (mod p)...

But in my problem, the number satisfy a^2=1(mod m) does not imply a=1 or m-1 since m is a composite number. (e.g. 3^2=1(mod 8))

I also modify my proof. Consider B^2=b1^2*b2^2*...bn^2. I have showed that for each bi, there exist unique bj such that bi*bj=1 (mod m) (similar to Wilsonís proof). Although we don't know bi is equal to bj or not.

So I divide the number into 2 groups,
1st group: bi*bj=1 (mod m) for i <>j
2nd group: bi*bj=1 (mod m) for i = j

So B^2 = 1 (mod m) but the same problem occurs,
It cannot be concluded that B= 1 or -1(mod m)

micromass
#4
Mar14-11, 09:26 PM
Mentor
micromass's Avatar
P: 18,099
Question from the proof in euler's forumla

Well, you could show the following:

For each bi, there exists a bj such that bibj=1 (mod m). If bi happens to equal bj, then there exists a br such that bibr=-1 (mod m).

So you can group the product into pairs again. Some pairs will multiply to 1 and some will multiply to -1.
lifom
#5
Mar15-11, 01:22 AM
P: 14
Quote Quote by micromass View Post
Well, you could show the following:

For each bi, there exists a bj such that bibj=1 (mod m). If bi happens to equal bj, then there exists a br such that bibr=-1 (mod m).

So you can group the product into pairs again. Some pairs will multiply to 1 and some will multiply to -1.
I get it! Thanks.
ramsey2879
#6
Mar15-11, 12:00 PM
P: 894
Quote Quote by micromass View Post
Well, you could show the following:

For each bi, there exists a bj such that bibj=1 (mod m). If bi happens to equal bj, then there exists a br such that bibr=-1 (mod m).

So you can group the product into pairs again. Some pairs will multiply to 1 and some will multiply to -1.
If bj^2 = 1 mod m then bj *(m -bj) = -1 mod m


Register to reply

Related Discussions
Proof of Euler's Theorem on Homogenous Functions Calculus & Beyond Homework 0
Proof of Euler's fuction. Linear & Abstract Algebra 3
A Proof of Euler Theorem Differential Geometry 0
Euler's polynomial proof Linear & Abstract Algebra 14
Euler's Forumla, Trig Addition, and Equating Coefficients General Math 3