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).
$\displaystyle k=\phi(n)$.

2. If m divides n, then m^2 divides n^2.
.
$\displaystyle 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
$\displaystyle k=\phi(n)$.

$\displaystyle 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]$\displaystyle 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
$\displaystyle 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 $\displaystyle \gcd(a,n)=1$ then $\displaystyle a^{\phi(n)}\equiv 1(\bmod n)$.
This is just a fancy way of saying $\displaystyle n| (a^{\phi(n)} - 1)$.
So if you pick $\displaystyle k=\phi(n)$ the proof follows.