Math Is Fun Forum

sam123

Guest

number theory

Hi this is from an old cryptography exam

Let n be an odd positive integer. Prove that (n-1)^(n-1)=1modn.    Does the same result hold if n is even?

Thanks for the help!

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: number theory

Hi sam123;

It does not hold for even numbers, you can find a small counterexample.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

sam123

Guest

Re: number theory

Cheers for that Bobby, now to prove it holds for odd positive integers, dont even know where to start=(

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: number theory

Hi sam123;

The demonstration could be done like this, since n is odd  and n > 1 then n - 1 is even.
So for (n-1)^(n-1) there are k groups of (n-1)^2 where k is some integer.
Remember n -1 is even. For instance  for n = 5 you have (4)^2 (4)^2. For n = 7 you have (6)^2 (6)^2 (6)^2.

So

Since

Now

So each

Then filling in B) we get 1 * 1 * 1 * 1 * 1... = 1

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

sam123

Guest

Re: number theory

Very nice Bobbym!! Thanks so much for the help

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: number theory

Glad to help! I am latexing it better right now.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.