# Thread: 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, $\displaystyle n^{13}\equiv{n}(\bmod7)$

I have written this:

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

because of Eulers theorem.

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

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

Thanks,

Katy

2. Originally Posted by harkapobi
Hi, I have this question,

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

I have written this:

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

because of Eulers theorem.

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

So $\displaystyle (n^6)^2\equiv{1}\bmod7)$
So $\displaystyle n\equiv{n}(\bmod7)$
And $\displaystyle 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 $\displaystyle 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!