Question from the proof in euler's forumla


by lifom
Tags: euler, forumla, proof
lifom
lifom is offline
#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
Lemurs match scent of a friend to sound of her voice
Repeated self-healing now possible in composite materials
'Heartbleed' fix may slow Web performance
micromass
micromass is offline
#2
Mar14-11, 08:18 PM
Mentor
micromass's Avatar
P: 16,518
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
lifom is offline
#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
micromass is offline
#4
Mar14-11, 09:26 PM
Mentor
micromass's Avatar
P: 16,518

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
lifom is offline
#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
ramsey2879 is offline
#6
Mar15-11, 12:00 PM
P: 891
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