Chris Tynan

Posted on Friday, 18 April, 2003 - 07:49 pm:

Using Euler's

φ

function, generalise Fermat's theorem that for a prime

p

a^{p - 1} = 1

mod (

p

)

The general theorem states that if $n$ is any integer and $a$ is relatively prime to $n$ then $a^{φ (n)} = 1$ mod[ $n$ ].

[Courant and Robbins, p.49]

Chris

David Loeffler

Posted on Friday, 18 April, 2003 - 09:39 pm:

Sorry, is this a question, or a statement? Do you want to know how to prove the generalised theorem?

Chris Tynan

Posted on Friday, 18 April, 2003 - 09:53 pm:

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

Posted on Friday, 18 April, 2003 - 10:03 pm:

The easy way to do this is with group theory. Can you see a group of order

φ (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 \in S$ , consider the set $T = a S = {a b : b \in S}$ . Can you see any obvious relation between the elements of $S$ and $T$ (as subsets of the integers mod $n$ )?

David

Chris Tynan

Posted on Saturday, 19 April, 2003 - 12:33 pm:

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

Posted on Saturday, 19 April, 2003 - 01:11 pm:

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

Posted on Saturday, 19 April, 2003 - 05:04 pm:

Right, I've really given this some thought now. I can see the case is obvious for

n

prime, since

φ (n) = n - 1

. Also, considering

a \in 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

Posted on Saturday, 19 April, 2003 - 06:55 pm:

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