I'm trying to solve a few problems and can't seem to figure them out. Since they are somewhat related, maybe solving one of them will give me the missing link to solve the others.

$(1)\ \ $ Prove that there's no $a$ so that $ a^3 \equiv -3 \pmod{13}$

So I need to find $a$ so that $a^3 \equiv 10 \pmod{13}$. From this I get that $$a \equiv (13k+10)^{1/3} \pmod{13} $$ If I can prove that there's no k so that $ (13k+10)^{1/3} $ is a integer then the problem is solved, but I can't seem to find a way of doing this.

$(2)\ \ $ Prove that $a^7 \equiv a \pmod{7} $

If $a= 7q + r \rightarrow a^7 \equiv r^7 \pmod{7} $. I think that next step should be $ r^7 \equiv r \pmod{7} $, but I can't figure out why that would hold.

$(3)\ \ $ Prove that $ 7 | a^2 + b^2 \longleftrightarrow 7| a \quad \textbf{and} \quad 7 | b$

Left to right is easy but I have no idea how to do right to left since I know nothing about what 7 divides except from the stated. Any help here would be much appreciated.

There're a lot of problems I can't seem to solve because I don't know how to prove that a number is or isn't a integer like in problem 1 and also quite a few that are similar to problem 3, but I can't seem to find a solution. Any would be much appreciated.

  • $\begingroup$ Do you know Fermat's Little Theorem? $\endgroup$ – Will Dana Oct 11 '11 at 0:48
  • $\begingroup$ I do, but I wasn't supposed to use it in this problems $\endgroup$ – Bananas Oct 12 '11 at 22:37

HINT $\rm\ (2)\quad\ mod\ 7\!:\ \{\pm 1,\:\pm 2,\:\pm3\}^3\equiv\: \pm1\:,\:$ so squaring yields $\rm\ a^6\equiv 1\ \ if\ \ a\not\equiv 0\:.$

$\rm(3)\quad \ mod\ 7\!:\ \ if\ \ a^2\equiv -b^2\:,\:$ then, by above, cubing yields $\rm\: 1\equiv -1\ $ for $\rm\ a,b\not\equiv 0\:.$

$\rm(1)\quad \ mod\ 13\!:\ \{\pm1,\:\pm3,\:\pm4\}^3 \equiv \pm 1,\ \ \{\pm2,\pm5,\pm6\}^3\equiv \pm 5\:,\: $ and neither is $\rm\:\equiv -3\:.$

If you know Fermat's little theorem or a little group theory then you may employ such to provide more elegant general proofs - using the above special cases as hints.

  • $\begingroup$ Sorry for taking so long to answer. Your hints were enough to solve this and a lot of problems like them. I know some group theory but can't come up with more elegant proofs, if it's not asking much a nudge in that direction would be great appreciated. Thanks very much for your help. $\endgroup$ – Bananas Oct 12 '11 at 22:38

For the first problem, an unimaginative but workable approach is just to check all the possibilities $a=0,1,2,\dots,12$. Do you see why, if these all fail, you're done?

For the 3rd problem, I think you mean right implies left is easy. For left implies right, take each of the numbers $0,1,\dots,6$, square them, divide by 7, and note the remainders. From that you can work out all the possible remainders of $a^2+b^2$, and from that you can answer the question.

Let me know if you've tried to work through this and found my hints too opaque.

  • $\begingroup$ Thanks for you help! Regarding the 3rd problem, I did mean that left to right is easy, to me at least. With Bill's hint I managed to solve it and then found another simple way of doing it. Again, thanks for taking the trouble to help. $\endgroup$ – Bananas Oct 12 '11 at 22:42

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.