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.

  • $\begingroup$ Are you familiar with the fact that $\mathbb{Z}/17\mathbb{Z}$ is a group? $\endgroup$ – Servaes Aug 19 '13 at 14:03
  • $\begingroup$ No sorry I'm not too sure, would you mind elaborating? Thanks for the reply. $\endgroup$ – KevinH Aug 19 '13 at 14:10
  • 1
    $\begingroup$ 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)$$ $\endgroup$ – Servaes Aug 19 '13 at 14:14
  • $\begingroup$ 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? $\endgroup$ – KevinH Aug 19 '13 at 15:10
  • $\begingroup$ 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 (: $\endgroup$ – 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$$

  • $\begingroup$ 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. $\endgroup$ – KevinH Aug 19 '13 at 14:33
  • $\begingroup$ $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. $\endgroup$ – Eleven-Eleven Aug 19 '13 at 14:37
  • $\begingroup$ 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. $\endgroup$ – KevinH Aug 19 '13 at 14:51
  • $\begingroup$ 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. $\endgroup$ – RghtHndSd Aug 19 '13 at 15:09
  • $\begingroup$ 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... $\endgroup$ – KevinH Aug 19 '13 at 15:24

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.