# Modular equation with very large powers

I studying for a discrete mathematics exam and am stuck on this question:

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

I have been reading up on how to solve similar problems but none that look similar to this. Can anyone help? Thank you very much.

• Are you familiar with the fact that $\mathbb{Z}/17\mathbb{Z}$ is a group? – Servaes Aug 19 '13 at 14:03
• No sorry I'm not too sure, would you mind elaborating? Thanks for the reply. – KevinH Aug 19 '13 at 14:10
• It means that the remainder of the sum of two integers after divison by $17$ equals the sum of their remainders after divison by $17$. The same holds for the product of two integers, in fact making $\mathbb{Z}/17\mathbb{Z}$ into a ring. This is true for division by any integer, not just $17$. This allows us to write the following: $$4^{1024000000002}=16^{512000000001}\equiv(-1)^{512000000001}\equiv-1\ (\operatorname{mod}17)$$ – Servaes Aug 19 '13 at 14:14
• Ok, I did a bit of searching and think I have an idea about what you mean, but how do I use that information to proceed? – KevinH Aug 19 '13 at 15:10
• This is your answer; clearly $-1\equiv16(\operatorname{mod}17)$. It might be insightful to read an introduction to modular arithmetic, and more importantly, to do many more of these exercises (: – Servaes Aug 19 '13 at 16:43

Hint: Note that $4^2 = -1 \mod 17$, so

$$4^{1024000000002} = (-1)^{1024000000002/2} \mod 17$$

This is because

$$4^{1024000000002} = (4^2)^{1024000000002/2} = 16^{1024000000002/2} = (-1)^{1024000000002 / 2} \mod 17$$

• I'm sorry, I'm new to this area of maths and I'm not sure exactly how you arrived at your second line, could you explain how the "/2" comes about? Thank you very much for your reply. – KevinH Aug 19 '13 at 14:33
• $4^2=16$. $16^{1/2}=4$ is probably a better way to put it. Thus, when he changes the base to 16, you must divide the exponent by 2 to create equivalent statements. – Eleven-Eleven Aug 19 '13 at 14:37
• Thank you very much :) I'm still a bit confused as to how I should proceed though, can anybody point me in the right direction, even in terms of what I should research on the web? I've spent the morning learning Chinese Remainder Theorem and that is pretty much the extent of what I know in regards to this topic, I really am not sure even how to describe what I am trying to do, apologies and thanks for your patience. – KevinH Aug 19 '13 at 14:51
• The CRT is not useful here. Perhaps the large number is throwing you off. Try this: $4^4 \equiv (4^2)^2 \equiv (-1)^2 \equiv 1 (\text{mod}\ 17)$ and now do $4^5$ yourself. If you can do that, I think you're ready for the original problem. – RghtHndSd Aug 19 '13 at 15:09
• The way I would do that is to go $4^5 = 1024$, therefore $4 ≡ x (mod 12), x = 4$ I'm assuming that that's not what you mean though... – KevinH Aug 19 '13 at 15:24