# Math Help - Show n^13 is congruent to n (mod7)

1. ## Show n^13 is congruent to n (mod7)

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

Thanks,

Katy

2. Originally Posted by harkapobi
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

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!