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

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

-
$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

$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.

-

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.

-
+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.

-

$\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}).$

-

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$.

-
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$).
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$.