Modular Arithmetic

Question

I am doing some exam preparation and can't figure out how to do the following question. It seems to be a regular question and was wondering if anyone who could tell me an approach to this style of question in laymen's term as everything tutorial i have found is either unrelated or over complicated. The question is as followed

Find the value of the unique integer $x$ satisfying $0\le x <17$ for which $$4^{102400000002}\equiv x \pmod{17}$$

Answer 1

Since $17$ is prime, we can apply Fermat's little theorem: $$ a^{17}\equiv a\pmod{17} $$ for any integer $a$. More useful is the statement that $$ a^{16}\equiv 1\pmod{17} $$ whenever $17$ is not a divisor of $a$. Since $4$ is not divisible by $17$, we can write $$ 102400000002=16\cdot 6400000000+2 $$ so $$ 4^{102400000002}=(4^{16})^{6400000000}\cdot 4^2\equiv 1\cdot16\pmod{17} $$

Answer 2

As $16\equiv-1\pmod{17}$

$$ 4^{102400000002}=(4^2)^{51200000001}\equiv(-1)^{51200000001}\pmod{17}\equiv?$$

We can generalize $102400000002$ with $4n+2$ where integer $n\ge0$

Answer 3

The fundamental idea is that when you exponentiate a number modulo $m$...

$$a^0, a^1, a^2, a^3... \mod m$$

You can't just keep getting different results, because all the values have to be between $0$ and $m-1$. So eventually you'll have to get a repeat, and from that point on, you get a repeating pattern. For example, modulo $10$, exponentiating $2$ goes like this:

$$1, 2, 4, 8, 6, 2, 4, 8, 6 ...$$

So to work out $4$ to the power of some massive number modulo $17$, we just look for the pattern:

$$1, 4, 16, 13, 1, 4...$$

So every $4$ multiplications, we get a repeat. So work out what that exponent is modulo $4$ and that'll tell you where in the cycle you'll be at that point.