2
$\begingroup$

Ever since I was introduced to modular arithmetic, I've had some trouble with it. I think it uses a part of my brain that I haven't used often. Anyways, I've been thinking about this specific equivalence: $$a^3 \equiv 5 \, (\text{mod } 7)$$ And I have a hunch that no $a$ exists s.t. this equivalence is true. Simulating it, it's clear that there is a pattern: 6, 1, 6, 6, 0, 1, 1, 6, 1, 6, 6, 0, 1, 1, 6, 1, 6, 6, 0...

But I can't figure out how to formally prove 1. that this pattern is the actual pattern and as an extension, 2. that the equivalence above doesn't hold (it should be trivial if I can prove 1).

Can anyone help? Thanks so much.

Improve this question
$\endgroup$
3
$\begingroup$

You can prove it by calculating the value of $a^3 \bmod 7$ for $a=0,1,2,3,4,5,6$; if none of those yield 5, then you have proven the claim.

Why is this sufficient? Well, if $a \equiv b \pmod 7$, then $a^3 \equiv b^3 \pmod 7$. So, if there was any solution to $a^3 \equiv 5 \pmod 7$, then you could take $b = a \bmod 7$, and that would be another solution. Now $b$ is one of $0,1,2,3,4,5,6$, so we've proven that if there is any solution, then one of $0,1,2,3,4,5,6$ must be a solution. Conversely, if none of $0,1,2,3,4,5,6$ is a solution, then there is no solution whatsoever.

For the special case of squaring (rather than cubing), you might be interested in quadratic reciprocity, which is a more advanced technique that allows to check for the existence of solutions to such an equation. There is also cubic reciprocity, though I'm not sure whether it leads to an efficient algorithm to check for solutions when you have a cube instead of a square.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Apparently cubic reciprocity is a thing. $\endgroup$ – Aaron Rotenberg Dec 15 '19 at 10:21
  • $\begingroup$ @AaronRotenberg, thanks! $\endgroup$ – D.W.♦ Dec 15 '19 at 18:17
  • $\begingroup$ I guess my misunderstanding is more fundamental. Why have we proven the claim if we've only tried 0 through 6? It's obvious that $a^1$ modulo 7 would "loop" back around, but how do we know it loops back around in the case of a cube? $\endgroup$ – CoolRobloxKid12 Dec 15 '19 at 19:49
  • $\begingroup$ @CoolRobloxKid12, ahh, that makes sense. See 2nd paragraph of my edited answer for an explanation of that point. $\endgroup$ – D.W.♦ Dec 15 '19 at 22:11
  • 1
    $\begingroup$ @CoolRobloxKid12, no, the opposite direction does not hold (consider that $1^3 \equiv 2^3 \pmod 7$), but we don't need it to. We know it's a solution because if you take $b = a \bmod 7$, then by construction $b \equiv a \pmod 7$; it follows that $b^3 \equiv a^3 \pmod 7$ (the magical fact that Aaron Rotenberg mentions); now since we know $a^3 \equiv 5 \pmod 7$, it follows that $b^3 \equiv 5 \pmod 7$, so $b$ is a solution, too. $\endgroup$ – D.W.♦ Dec 16 '19 at 2:20

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.