0
$\begingroup$

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}$$

$\endgroup$
2
$\begingroup$

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} $$

$\endgroup$
4
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.