# Math Help - 2 Questions please

Thanks for the help last time, I have 2 questions that I know are easy but I am hitting a block with all of my exams going on right now anyway..

1. Show that if a,n are positive integers and gcd(a,n)=1, then there exists a positive integer k, such that n divides((a^k)-1).

This one I should know but I can't seem to come up with the right procedure....
2. If m divides n, then m^2 divides n^2.

2. Originally Posted by jonnyfive
1. Show that if a,n are positive integers and gcd(a,n)=1, then there exists a positive integer k, such that n divides((a^k)-1).
$k=\phi(n)$.

2. If m divides n, then m^2 divides n^2.
.
$m|n\implies n=m\cdot a \implies n^2 = m^2 \cdot a^2 \implies m^2|n^2$

3. Originally Posted by ThePerfectHacker
$k=\phi(n)$.

$m|n\implies n=m\cdot a \implies n^2 = m^2 \cdot a^2 \implies m^2|n^2$

Thank you for your help, thats what I thought I was suppose to do for the second one but I thought there was more to it.

On the first one all I need to know is that k= phi(n)?

4. [quote=ThePerfectHacker;141411] $k=\phi(n)$.

any chance i can get you to explain this...I can't believe it can be this simple

5. Originally Posted by jonnyfive
Thank you for your help, thats what I thought I was suppose to do for the second one but I thought there was more to it.

On the first one all I need to know is that k= phi(n)?
Originally Posted by theotheleo
Originally Posted by ThePerfectHacker
$k=\phi(n)$.

any chance i can get you to explain this...I can't believe it can be this simple
This is Euler's Theorem if $\gcd(a,n)=1$ then $a^{\phi(n)}\equiv 1(\bmod n)$.
This is just a fancy way of saying $n| (a^{\phi(n)} - 1)$.
So if you pick $k=\phi(n)$ the proof follows.