Congruence identities using Fermat's Little Theorem

[tomwilliam]

Homework Statement

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

Homework Equations

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

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

 

[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.

 

[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...

 

[scurty]

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