Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Do you know Fermat's Little Theorem? –  William D. 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
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.