5
$\begingroup$

What is the remainder of $(14^{2010}+1) \div 6$?

Someone showed me a way to do this by finding a pattern, i.e.:

$14^1\div6$ has remainder 2
$14^2\div6$ has remainder 4
$14^3\div6$ has remainder 2
$14^4\div6$ has remainder 4

And it seems that when the power is odd, the answer is 2, and when it's even, the answer is 4.

2010 is even, so the remainder is 4, but we have that +1, so the final remainder is 5. Which is correct.

But this method doesn't seem very concrete to me, and I have a feeling the pattern may not be easy to find (or exist?) for every question. What theorem or algorithm can I use to solve this instead?

5 Answers 5

10

$14\equiv 2\pmod 6$, so $14^{2010}+1\equiv 2^{2010}+1\pmod 6$. Now $2\cdot 2^2=2^3=8\equiv 2\pmod 6$, so $2\cdot (2^2)^k\equiv 2\pmod 6$ for any non-negative integer $k$. This shows that the pattern that you observed is real: $2^{2k+1} \equiv 2\pmod 6$ for any non-negative integer $k$. In particular, $$2^{2010}+1\equiv 2\cdot 2^{2009}+1 \equiv 2\cdot 2+1 \equiv 5\pmod 6\;.$$

The same basic idea can be used in similar problems, though the cycle of the pattern may not be nearly so short. To go much deeper than this kind of analysis, you want to look into the Chinese Remainder Theorem.

  • 0
    Why is $2\cdot (2^2)^k\equiv 2\pmod 6$?2015-07-29
  • 0
    Also why is $2^{2009}+1 \equiv 2\cdot 2+1$?2015-07-29
  • 0
    @user103816: The first follows by induction on $k$: it’s true for $k=1$, and if it’s true for $k$, then $2\cdot(2^2)^{k+1}=\left(2\cdot(2^2)^k\right)\cdot2^2\equiv 2\cdot 2^2\equiv 2\pmod6$, so it’s true for $k+1$. It doesn’t say that $2^{2009}+1\equiv 2\cdot2+1\pmod6$; it says that $2\cdot2^{2009}+1\equiv 2\cdot2+1\pmod6$, which is true because $2^{2009}=2^{2\cdot 1004+1}\equiv 2\pmod6$.2015-07-29
  • 0
    I don't get it. How is $2\cdot(2^2)^{k+1}=\left(2\cdot(2^2)^k\right)\cdot2^2\equiv 2\cdot 2^2\equiv 2\pmod6$? and how is $2^{2009}=2^{2\cdot 1004+1}\equiv 2\pmod6$?2015-07-30
  • 0
    @user103816: You’ll have to be more explicit, I’m afraid. Every step there is explained either in the original answer or in my previous comment, so I can’t tell exactly what part(s) you’re not understanding.2015-07-30
  • 0
    Being more explicit I am asking why remainder of $(2\cdot(2^{2k})\cdot 2^2)$ when divided by $6$ is $2$. And why the remainder of $2^{2009}$ when divided by $6$ is $2$--And does this fact imply that the remainder of $2\cdot 2^{2009}$ when divided by $6$ is $2$? Btww... I guess it can be shown by using $ab \pmod N= {r_a}{r_b} \pmod N$.2015-07-31
  • 0
    @user103816: The induction hypothesis is that $2\cdot2^{2k}\equiv2\pmod6$. Therefore $\left(2\cdot2^{2k}\right)\cdot2^2\equiv2\cdot2^2\pmod6$. And $2\cdot2^2=8\equiv2\pmod6$. That induction proves the general result that $2\cdot2^{2k}\equiv2\pmod6$. I don’t know where you got the idea that $2^{2009}\equiv2\pmod6$: it’s not in anything that I’ve said. However, $2^{2009}=2\cdot2^{2008}=2\cdot2^{2\cdot1004}\equiv2\pmod6$ by that general result proved by induction on $k$.2015-07-31
  • 0
    Which property are you using for showing $\left(2\cdot2^{2k}\right)\cdot2^2\equiv2\cdot2^2\pmod6$?2015-08-01
  • 0
    @user103816: I’m simply using the fact that $2\cdot2^{2k}\equiv2\pmod6$ and the very basic fact that if $a\equiv b\pmod{m}$ and $c\equiv d\pmod{m}$, then $a+c\equiv b+d\pmod{m}$.2015-08-01
  • 0
    Means that you are kind of using $a \pmod m =r_a \implies Na\pmod m = Nr_a \pmod m$, where $N$ is any positive integer.2015-08-02
  • 0
    @user103816: Not really, no.2015-08-02
  • 0
    I am not able to understand how the fact that "if $a\equiv b\pmod{m}$ and $c\equiv d\pmod{m}$ then $a+c\equiv b+d\pmod{m}$ $\implies \left(2\cdot2^{2k}\right)\cdot2^2\equiv2\cdot2^2\pmod6$. As far as I could understand it, I thought $a≡b(\mod m) = (2 \cdot 2^{2k}≡2 \mod 6$ and $a+a≡2+2≡(2\cdot 2) \mod 6$.2015-08-03
4

$14=0\pmod{2}$ and $14=2\pmod{3}$. Thus, because $2^2=1\pmod{3}$, for any $k>0$, we have $$ 14^k=0\pmod{2} $$ and $$ 14^k=\left\{\begin{array}{}1\pmod{3}&\text{when }k=0\pmod{2}\\2\pmod{3}&\text{when }k=1\pmod{2}\end{array}\right. $$ Therefore, for any $k>0$, we have by the Chinese Remainder Theorem, $$ 14^k=\left\{\begin{array}{}4\pmod{6}&\text{when }k=0\pmod{2}\\2\pmod{6}&\text{when }k=1\pmod{2}\end{array}\right. $$ So, as you surmised, $14^{2010}+1=5\pmod{6}$.

2

To solve this problem, in general, I'd use use two facts:

  1. If $a$ and $n$ are relatively prime, $a^{\phi(n)} \bmod n = 1$. Here $\phi$ is the Euler phi function; when $n$ is prime, $\phi(n) = n-1$. This lets you reduce exponents to ones with power less than $\phi(n)$; for instance $$2^{2010} \bmod 5 = (2^4)^{502} 2^2 \bmod 5 = 1^{502} 4 \bmod 5 = 4.$$ (Here $2^2$ happened to be trivial to compute by hand; if the exponent were larger I would calculate it using the technique of repeated squaring.)

  2. Unfortunately 2 and 6 are not relatively prime; in this case I would factor $6$ into primes and use the Chinese remainder theorem: $$2^{2010} \bmod 3 = (2^2)^{1005} \bmod 3 = 1$$ $$2^{2010} \bmod 2 = 0$$ so applying the Chinese remainder theorem, $2^{2010}$ must be congruent to 4 mod 6.

1

We may write following equalities :

$14^{2010}=6\cdot k_1+4$

$14^{2010}+1=6\cdot k_2+r$

$6\cdot k_1+4+1=6\cdot k_2+r\Rightarrow 6k_1+5=6k_2+r$

The last equality is true only if $k_1=k_2$ and $r=5$

  • 1
    Please excuse my ignorance, but it looks to me like you *assumed* that $14^{2010} = 4 \mod 6$, and then use this to 'prove' that $14^{2010} + 1 = 5 \mod 6$. How do you justify the first equality given $k_1$ is an integer?2011-11-06
  • 0
    @tom,read carefully text of the question...2011-11-06
1

HINT $\rm\quad (m,n) = 1,\ m\:|\:a,\ n\:|\:a+1\ \ \Rightarrow\ \ a^{2\:k}\ \equiv\ m\:(m^{-1}\ mod\ n)\ \pmod{mn}\ $ by CRT.

Therefore for $\rm\:m,n,a\ =\ 2,3,14\:$ we infer $\rm\: 14^{\:2\:k} \equiv\: 2\ (2^{-1}\ mod\ 3)\equiv -2\pmod 6$