Show n^13 is congruent to n (mod7)

harkapobi · #1 $Old$ November 5th, 2009, 03:15 AM

Hi, I have this question,

Show that for any integer n, $n^{13}\equiv{n}(\bmod7)$

I have written this:

$n^{6}\equiv{1}(\bmod7)$

because of Eulers theorem.

$n^{13} = (n^6)^2n$

So $(n^6)^2\equiv{1}(\bmod7)$
So $n\equiv{n}(\bmod7)$
And $0\equiv{0}(\bmod7)$ QED

Is this right? Please help.

Thanks,

Katy

tonio · #2 $Old$ November 5th, 2009, 04:39 AM

Quote:

Originally Posted by harkapobi $View Post$

Hi, I have this question,

Show that for any integer n, $n^{13}\equiv{n}(\bmod7)$

I have written this:

$n^{6}\equiv{1}(\bmod7)$

because of Eulers theorem.

$n^{13} = (n^6)^2n$

So $(n^6)^2\equiv{1}\bmod7)$
So $n\equiv{n}(\bmod7)$
And $0\equiv{0}(\bmod7)$ QED

Is this right? Please help.

Thanks,

Katy

It was going fine but then I didn't understand what you did at the end: so you have that $n^6=1\!\!\!\!\pmod 7\Longrightarrow n^{12}=1\!\!\!\!\pmod 7$ ....so now just multiply by n both sides in the last congruence and we're done!

Tonio

harkapobi · #3 $Old$ November 5th, 2009, 06:25 AM

Ahhh yes! Thank you

Can't believe I didn't see that.