Congruence identities using Fermat's Little Theorem

1. Apr 15, 2012

tomwilliam

1. The problem statement, all variables and given/known data

Show the remainder when 43^43 is divided by 17.

2. Relevant equations

$$43 = 16 \times 2 + 11$$
$$a^{p-1}\equiv1\ (mod\ p)$$

3. The attempt at a solution

I believe I can state at the outset that as:
$$43\equiv9\ (mod\ 17)$$
Then
$$43^{43}\equiv9^{43}\ (mod\ 17)$$
and that I can rewrite this as:
$$9^{43}=\left(9^{2}\right)^{16}\times9^{11}$$
Then applying Fermat's Little Theorem we get:
$$\left(9^{2}\right)^{16}\equiv1\ (mod\ 17)$$
So that
$$43^{43}\equiv 1\times9^{11}\ (mod\ 17)$$
But I'm unsure where to go from here.
Any help appreciated

2. Apr 15, 2012

scurty

There are numerous ways to go about solving the problem from this kind of point. You just try to simplify the numbers more and more. A nice way I found to solve this is to consider $9^2 (mod 17)$. You can simplify the problem nicely in the next step after that.

3. Apr 15, 2012

tomwilliam

Thanks for taking the time out.
I feel like I'm probably not far away!

$$9^2\equiv13\ (mod\ 17)$$

So I guess I can consider $$9^{11}=\left(9^2\right)^5\times9$$ and simplify to:

$$43^{43}\equiv13^5\times 9$$

But still unsure how to proceed. I'll have another think...

4. Apr 15, 2012

scurty

Okay, good! What is another way of writing 13 mod 17?