Euler's theorem proof help

**Nguyen** · May 6th 2011, 05:44 AM

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

**tonio** · May 6th 2011, 08:27 AM

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

**abhishekkgp** · May 6th 2011, 09:25 AM

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?

**Deveno** · May 6th 2011, 10:16 AM

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

**Nguyen** · May 6th 2011, 05:19 PM

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.

**Deveno** · May 6th 2011, 06:44 PM

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

Thread: Euler's theorem proof help

LinkBack

Thread Tools

Display

Euler's theorem proof help

Similar Math Help Forum Discussions

abstract algebra [primitive root mod n, euler theorem, fermat theorem]

One more Euler theorem proof

Euler's Theorem

Euler's Theorem

Euler's Theorem

Search Tags