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.

Suppose that today is tuesday. what day of the week will it be in $3^{100000} + 3^{10000} + 3^{1000}$ days ?

I figured that, eventually, I will add $3^{100000} + 3^{10000} + 3^{1000}$ and $\mod\ 7$ that answer...

I tryed with the Fermat little theorem but cant quit figure how to apply it here.

$m = n(\mod p-1)$ then , $a^m = a^n (\mod p)$

doing that I realised that $3^{x} \mod 7 = 4$ for all $x \mod 10 = 0$

when I try to apply Fermat, I end up with :

$m = 100000 \mod 6 = 4 \\ 3^4 = 3^{100000} \mod 7 $

which make no sense...

Am I using the right theorem for the problem ? If so, how do I apply it...

Thanks

share|improve this question
    
$3^6 = 1 \mod 7$. –  copper.hat Feb 13 '13 at 17:18
    
Yes, $3^4$ and $3^{100000}$ give the same remainder modulo $7$. –  Berci Feb 13 '13 at 17:19

7 Answers 7

up vote 1 down vote accepted

$3^6 = 1 \mod 7$. Hence $3^k \mod 7 = 3^{k-6n} \mod 7$.

$100000 = 6\cdot 16666 + 4$. $10000 = 6\cdot 1666 + 4$. $1000 = 6\cdot 166 + 4$. Hence $3^{100000} + 3^{10000} + 3^{1000} \mod 7 = 4+4+4 \mod 7 = 5 \mod 7$.

Hence it will be Sunday.

share|improve this answer

Negative numbers are handy here. Use the fact that $3^3\equiv -1 \pmod{7}$ (easily checked: $27=28-1$).

Since $3^{999\dots 9}$ ($k$ $9$'s) is $(3^3)^{333\dots 3}$ ($k$ $3$'s), we have $3^{999\dots 9}\equiv -1\pmod{7}$, and therefore $3^{1000\dots 0}$ ($k$ $0$'s) is congruent to $-3$.

We have three such terms in our sum. The sum is therefore congruent to $-9$ modulo $7$, and therefore to $-2$.

So count backwards by $2$ from Tuesday.

share|improve this answer
    
+1 Very cute. ${}{}{}$ –  copper.hat Feb 13 '13 at 17:27

As you have noticed, from little Fermat, we have $$3^6 \equiv 1 \pmod 7$$ Now $10^k \equiv 4 \pmod6$. Hence, $$3^{10^k} \pmod 7 \equiv 3^{6m+4} \pmod 7 \equiv \left(3^{6}\right)^m \cdot 3^4 \pmod 7 \equiv 3^4 \pmod7 \equiv 4 \pmod 7$$ Now you should be able to conclude the answer.

share|improve this answer

$\rm mod\ 7\!:\ 3^3\equiv -1\Rightarrow 3^6 \equiv 1\Rightarrow3^n\equiv 3^{(n\ mod\ 6)}.\:$ $\rm\:mod\ 6\!:\ 10\equiv 4,\ 4^2\equiv 4 \Rightarrow \color{#0A0}{10^k}\equiv 4^k\equiv \color{#C00}4,\:$ so

$\rm mod\ 7\!:\ 3^{\color{#0A0}{10^I}}\!+3^{\color{#0A0}{10^J}}\! + 3^{\color{#0A0}{10^K}}\!\equiv 3^{\color{#C00}4}\! + 3^{\color{#C00}4}\! + 3^{\color{#C00}4 }\equiv 3\cdot 3^{4}\equiv 3(-3)\equiv \color{blue}{\bf -2}\ $ for $\rm\ I,J,K > 0.$

Therefore the day of the week will be two days prior $\rm(\color{blue}{\bf -2}\ mod\ 7)$ to Tuesday, i.e. Sunday, and the stated result holds true more generally for exponents being arbitrary powers of $10\,$ (except $\,10^{\,0}).$

share|improve this answer

Yes, exactly. $3^2\equiv 2$, $\ 3^3\equiv 2\cdot 3\equiv -1$, and so on, you will get $3^6=(3^3)^2\equiv 1$ mod $7$ indeed.

The point is that we are not using the $mod$ operation as a binary operation, but instead we use congruences, saying that numbers $a,b$ are congruent modulo $m$ iff they give the same remainder, or more simply and exactly iff $m|b-a$.

share|improve this answer

There's another way you can approach this. Note that $3^0,3^1,3^2,3^3,...$ go through a specific pattern, modulo $7$. Determine precisely how this pattern proceeds, and you'll be able to say what each of $3^{1000},3^{10000},3^{100000}$ are (modulo $7$), which will tell you what their sum is (modulo $7$).

share|improve this answer

Note that modulo 7, $3^{10} = 3^3 = 27 = -1$. Hence, $3^{100000} + 3^{10000} + 3^{1000} = (3^{10})^{100} \left(1 + 3^{10}(1 + 3^{10}) \right) = (-1)^{100} \left(1 - (1 - 1) \right) = 1$.

share|improve this answer

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.