Elementary Number Theory Exercises

[Ender]

Here's some exercises I made up while on my way and eating dinner at a restaurant =) No calculators allowed.

1. Find the remainder when 3^1337 is divided by 7.

2. Find the remainder when 13^37 is divided by 49.

I really like the second one :P I think it's cooler.

Solutions posted.

[Ender]

I forgot to say that you should, of course, post a solution with your answer.

EDIT: I will post the solution in a week on Thursday (a week is too long, and I would post it earlier but some people may not see the thread before then).

[rabbit]

The first is 1.

I don't feel like remembering how to do 13^37 :\

[Ender]

Your answer is wrong.

I forgot to say that you should, of course, post a solution with your answer.

[rabbit]

Your answer is wrong.

I forgot to say that you should, of course, post a solution with your answer.

Your answer is wrong.

[Sidoh]

Your answer is wrong.

Mathematica says you're wrong too. ;)

Ender, I'll think about it a bit.

[Ender]

Solution to 1:

Answer: 5

Solution: We can use modular arithmetic and express our remainder as [tex]r = 3^{1337} \pmod{7}[/tex]. Since 3 is coprime to 7, we can use Fermat's Little Theorem, and we find that [tex]3^6 \equiv 1 \pmod{7}[/tex]. We see that [tex]6 | 1332[/tex] since 1332 is even and 1+3+3+2=9. It follows that that for some integer k, we have [tex]r = 3^{1337} = 3^{6k + 5} = 3^{6k} * 3^{5} \equiv 1 * 3^{5} \pmod{7}[/tex], greatly simplifying the problem.

For the last step,

[tex]r = 3^{5} = \frac{3^{6}}{3} \equiv \frac{1}{3} \pmod{7}[/tex]. Thus [tex]3r \equiv 1 \pmod{7}[/tex]. By observation we see that r=5 satisfies this linear congruence, so the remainder is 5.

This looks long because I wrote out all the steps, but it can be done in the head pretty fast. Another way to do this is to make a table of remainders for small powers until it repeats. Since this table will be periodic, you can predict the remainder for larger powers. This alternate way doesn't require much knowledge of number theory.

[Ender]

Solution to 2:

Answer: 27 (revised)

We have [tex]r = 13^{37} \pmod{49}[/tex]. Note that 13 is coprime to 49 and that [tex]\phi(49) = 7^{2} - 7 = 42[/tex]. By Euler's Theorem, we can simplify this to [tex]r \equiv 13^{-5} \pmod{49}[/tex] and so [tex]13^{5}r \equiv 1 \pmod{49}[/tex]. We can calculate [tex]13^{2} \equiv 22 \pmod{49}[/tex] to get [tex]13^{4} \equiv -6 \pmod{49}[/tex] and finally [tex]13^{5} \equiv 20 \pmod{49}[/tex]. Thus we have [tex]13^{5} r \equiv 20 r \equiv 1 \pmod{49}[/tex]. This seems like a hard linear congruence to solve, but it's much easier if you notice that 9*49 must be one more than a multiple of 20, since 40 is a multiple of 20 and 9*9 = 80 + 1. We have 9*49 = 360 + 81 = 441, so [tex]20*22 \equiv -1 \pmod{49}[/tex] shows us that [tex]20*(-22) \equiv 1 \pmod{49}[/tex]. Making that positive, we see that r = 27.

I actually meant to make this problem easier, but when I did it out I saw that there were some computational obstacles (which still can be done by hand fairly easily, as is what I did). I may have made an arithmetic mistake though, so it would be cool if someone checked this on Mathematica. So for a followup problem:

What is the remainder when you divide 13^43 by 49?

This problem has a one-line solution. Hint: Euler's Theorem.

[Ender]

What is the remainder when you divide 13^43 by 49?

Solution. [tex]\phi(49) = 7^{2} - 7 = 42[/tex]. Since 13 is coprime to 49, we can employ Euler's Theorem, and we find that [tex]13^{42} \equiv 1 \pmod{49}[/tex]. It follows that [tex]13^{43} \equiv 13 \pmod{49}[/tex], so 13 is the remainder.

This is what is considered a "one-liner" in math. If you want, it can be written in one-line with less clarification :P