
#1
Mar1411, 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)? 



#2
Mar1411, 08:18 PM

Mentor
P: 16,518

Have you seen Wilson's theorem? This states that (p1)!=1 (mod p) for prime p.
Can you adjust the proof so that it also works in this case? 



#3
Mar1411, 09:18 PM

P: 14

In Wilson's proof, the number satisfy a^2=1(mod p) > (a1)(a+1) = p*n. Since 0<=a<p a= 1 or p1 only. So for 2,3,...,p2, 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 m1 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) 



#4
Mar1411, 09:26 PM

Mentor
P: 16,518

Question from the proof in euler's forumla
Well, you could show the following:
For each b_{i}, there exists a b_{j} such that b_{i}b_{j}=1 (mod m). If b_{i} happens to equal b_{j}, then there exists a b_{r} such that b_{i}b_{r}=1 (mod m). So you can group the product into pairs again. Some pairs will multiply to 1 and some will multiply to 1. 



#5
Mar1511, 01:22 AM

P: 14





#6
Mar1511, 12:00 PM

P: 891




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 