# Euler's theorem proof help

• May 6th 2011, 06:44 AM
Nguyen
Euler's theorem proof help
Hey, I am having a difficult time trying to prove a few statements relating to Euler's Theorem.

1. Prove for any n: If $x,y$ are in $\Phi_n$ , then $xy \ mod \ n$ is also in $\Phi_n$, using a contrapositive argument.

2. Prove: Every $a \in \Phi_n$ has an inverse modulo n in $\Phi_n$ , by considering the linear congruence $ax \equiv 1 (mod \ n)$

3. Prove: For every $a \in \Phi_n$ the function $f_a : \Phi_n \to\Phi_n$ defined by $f_a(x) =ax$ is a permutation.

I really don't know what to do for these.
Any help would be greatly appreciated.

Thanks
• May 6th 2011, 09:27 AM
tonio
Quote:

Originally Posted by Nguyen
Hey, I am having a difficult time trying to prove a few statements relating to Euler's Theorem.

1. Prove for any n: If $x,y$ are in $\Phi_n$ , then $xy \ mod \ n$ is also in $\Phi_n$, using a contrapositive argument.

2. Prove: Every $a \in \Phi_n$ has an inverse modulo n in $\Phi_n$ , by considering the linear congruence $ax \equiv 1 (mod \ n)$

3. Prove: For every $a \in \Phi_n$ the function $f_a : \Phi_n \to\Phi_n$ defined by $f_a(x) =ax$ is a permutation.

I really don't know what to do for these.
Any help would be greatly appreciated.

Thanks

It's be great if you'd tell us what in the world do you call $\Phi_n$ to...(Headbang)(Punch)

Tonio
• May 6th 2011, 10:25 AM
abhishekkgp
Quote:

Originally Posted by Nguyen
Hey, I am having a difficult time trying to prove a few statements relating to Euler's Theorem.

1. Prove for any n: If $x,y$ are in $\Phi_n$ , then $xy \ mod \ n$ is also in $\Phi_n$, using a contrapositive argument.

2. Prove: Every $a \in \Phi_n$ has an inverse modulo n in $\Phi_n$ , by considering the linear congruence $ax \equiv 1 (mod \ n)$

3. Prove: For every $a \in \Phi_n$ the function $f_a : \Phi_n \to\Phi_n$ defined by $f_a(x) =ax$ is a permutation.

I really don't know what to do for these.
Any help would be greatly appreciated.

Thanks

i believe http://latex.codecogs.com/png.latex?\Phi_n is the set of all positive integers (including 1) relatively prime to n.
For the first one:
given that http://latex.codecogs.com/png.latex?gcd(x,n)=1 so there exist integers http://latex.codecogs.com/png.latex?a\, and \, b such that http://latex.codecogs.com/png.latex?ax+bn=1. similarly there exist integers http://latex.codecogs.com/png.latex?c\, and \, d such that http://latex.codecogs.com/png.latex?cy+dn=1. Multiplying the two equations we have:
http://latex.codecogs.com/png.latex?... \,gcd(xy,n)=1.

The second part follows again from the fact that if http://latex.codecogs.com/png.latex?gcd(a,n)=1 then there exist integers http://latex.codecogs.com/png.latex?x_1\, and \, y_1 such that http://latex.codecogs.com/png.latex?ax_1+ny_1=1. Note that http://latex.codecogs.com/png.latex?...,(\,mod\,n\,).. hence http://latex.codecogs.com/png.latex?x_1\,(\,mod\,n\,) is the http://latex.codecogs.com/png.latex?x you want.

for the third one you need to show that http://latex.codecogs.com/png.latex?f_a is bijective. can you do it?
• May 6th 2011, 11:16 AM
Deveno
hint for number 3: $\Phi_n$ is a finite set. therefore you only need to show that $f_a$ is surjective (why?)

now use part (2).
• May 6th 2011, 06:19 PM
Nguyen
Sorry Tonio, $\Phi_n = \{x: 1 \le x < n, gcd(x,n)=1 \}$

Quote:

Originally Posted by abhishekkgp
i believe http://latex.codecogs.com/png.latex?\Phi_n is the set of all positive integers (including 1) relatively prime to n.
For the first one:
given that http://latex.codecogs.com/png.latex?gcd(x,n)=1 so there exist integers http://latex.codecogs.com/png.latex?a\, and \, b such that http://latex.codecogs.com/png.latex?ax+bn=1. similarly there exist integers http://latex.codecogs.com/png.latex?c\, and \, d such that http://latex.codecogs.com/png.latex?cy+dn=1. Multiplying the two equations we have:
http://latex.codecogs.com/png.latex?... \,gcd(xy,n)=1.

The second part follows again from the fact that if http://latex.codecogs.com/png.latex?gcd(a,n)=1 then there exist integers http://latex.codecogs.com/png.latex?x_1\, and \, y_1 such that http://latex.codecogs.com/png.latex?ax_1+ny_1=1. Note that http://latex.codecogs.com/png.latex?...,(\,mod\,n\,).. hence http://latex.codecogs.com/png.latex?x_1\,(\,mod\,n\,) is the http://latex.codecogs.com/png.latex?x you want.

for the third one you need to show that http://latex.codecogs.com/png.latex?f_a is bijective. can you do it?

Thanks abhishekkgp, I fully understand the first one now. Is that all the working for the second one? I think I understand it.

I can see that for the third one, that it is surjective and because the set is finite it is therefore bijective, but I don't get how to work it out properly.

Any help here?

Thanks so much for your help.
• May 6th 2011, 07:44 PM
Deveno
a permutation of $\Phi_n$ IS a bijection on $\Phi_n$. and you know that $f_a$ is a surjection why? this is where part (2) comes in.

if for every a, we have an x with ax = 1 (mod n), then suppose y is any (arbitrary) element of $\Phi_n$.

what is $f_a(xy)$?