# Math Help - Euler's theorem proof help

1. ## 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

2. 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...

Tonio

3. 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 $\Phi_n$ is the set of all positive integers (including 1) relatively prime to n.
For the first one:
given that $gcd(x,n)=1$ so there exist integers $a\, and \, b$ such that $ax+bn=1$. similarly there exist integers $c\, and \, d$ such that $cy+dn=1$. Multiplying the two equations we have:
$(ca)xy+(axd+bcy+bdn)n=1 \Rightarrow \,gcd(xy,n)=1$.

The second part follows again from the fact that if $gcd(a,n)=1$ then there exist integers $x_1\, and \, y_1$ such that $ax_1+ny_1=1$. Note that $ax_1 \equiv 1\,(\,mod\,n\,).$. hence $x_1\,(\,mod\,n\,)$ is the $x$ you want.

for the third one you need to show that $f_a$ is bijective. can you do it?

4. 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).

5. Sorry Tonio, $\Phi_n = \{x: 1 \le x < n, gcd(x,n)=1 \}$

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

The second part follows again from the fact that if $gcd(a,n)=1$ then there exist integers $x_1\, and \, y_1$ such that $ax_1+ny_1=1$. Note that $ax_1 \equiv 1\,(\,mod\,n\,).$. hence $x_1\,(\,mod\,n\,)$ is the $x$ you want.

for the third one you need to show that $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.

6. 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)$?