# A couple of problems involving divisibility and congruence

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.

• Do you know Fermat's Little Theorem? – Will Dana Oct 11 '11 at 0:48
• I do, but I wasn't supposed to use it in this problems – 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.

• 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. – 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.

• 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. – Bananas Oct 12 '11 at 22:42