| Chris
Tynan |
Using Euler's j function, generalise Fermat's theorem that for a prime p, ap-1=1 mod (p) The general theorem states that if n is any integer and a is relatively prime to n then aj(n)=1 mod[n]. [Courant and Robbins, p.49] Chris |
||
| David
Loeffler |
Sorry, is this a question, or a statement? Do you want to know how to prove the generalised theorem? |
||
| Chris
Tynan |
This is exactly how it appeared in the book. I'd like a prove of the formula, although I think I might be able to fathom one out, but I thought a further generalisation was implied, from the wording. So, yes, I'd like a decent kick to help me prove the generalised theorem. Sorry about the ambiguity. Chris |
||
| David
Loeffler |
The easy way to do this is with group theory. Can you see a group of order j(n) anywhere obvious? Alternatively: consider the set S of b in (1..n) such that hcf(b,n)=1. Let a be any of these. For any a Î S, consider the set T=a S={a b:b Î S}. Can you see any obvious relation between the elements of S and T (as subsets of the integers mod n)? David |
||
| Chris
Tynan |
Hmm, I'm not sure if I follow either part too well. I think I'm going to need a full explanation. Chris |
||
| Demetres
Christofides |
Have you ever seen a proof of Fermat's little theorem ? Do you think you can generalize it ? Hint 1: Lagrange's theorem. (If you want to use group theory) Hint 2: Bezout's lemma. If a,b are coprime then there are integers x,y such that ax + by = 1. Demetres |
||
| Chris
Tynan |
Right, I've really given this some thought now. I can see the case is obvious for n prime, since j(n)=n-1. Also, considering a Î S, where S is the set mentioned earlier, I can also see it's clear that a x=1 mod n for some integer x, but I just can't see how to go on, I'm real stuck here. Demetres, the only prove I've seen of fermat's little theorem is that in Courant & Robbins, which uses (p-1) multiples of a, and proceeds to show these multiples are congruent to 1,2,...p-1 mod p in some order, and uses this this result to prove the theorem. Chris |
||
| Demetres
Christofides |
Great, that's exactly the proof I wanted you to know ! The generalization of this to the proof of Euler's theorem is immediate. However if you still want another hint you can find one below. (Don't look at it before trying the problem again). Demetres If a and b are coprime to n then so is ab |