Last digits number theory. $7^{9999}$?

i have looked at/practiced several methods for solving ex: $7^{9999}$. i have looked at techniques using a)modulas/congruence b) binomial theorem c) totient/congruence d) cyclicity.

my actual desire would be a start to finish approach using totient/congruence. i have figured out how to work the individual steps but not how to combine them and in what order to be able to solve any "end digits" questions.

• How many final digits do you seek? – Bill Dubuque Jan 1 '14 at 0:45
• 1 - 3 is what i would like to be able to solve – user118512 Jan 1 '14 at 0:54
• Generally you use Euler's theorem to reduce the exponent modulo $\,\phi(10^n)\,$ or $\,\lambda(10^n),\,$ where $\,n\,$ is the number of final digits. Any simplifications after that are that are generally ad-hoc, depending on the specifics of the problem. – Bill Dubuque Jan 1 '14 at 0:57
• ex: i can find ϕ(1000)=400, but do not know ad-hoc steps to follow after that? thks – user118512 Jan 1 '14 at 1:02
• Also, you could choose generators of the multiplicative group, and build tables rules, etc. For example, John Conway and I devised a simple way to do this for $\,\Bbb Z/100^{\,*},$ which makes it very easy to compute powers and roots/logs etc. I call them the lucky $7$-$11$ logs (the generators $7$ and $11$ prove very convenient). – Bill Dubuque Jan 1 '14 at 1:04

Note:

$7^4$ ends in $1$

So, $7^8$, $7^{12}$, $7^{16}$ all end in $1$.

So, $7^{9996}$ ends in $1$. And $7^3$ ends in $3$. So, the answer is $3$

I have used the fact that $$\phi(10) = 4$$ where $\phi$ is the totient function.

Note: Added in response to OP's comment

If we want the last two digits, we note that $\phi(1000)=400$. So $$9999 = 9600 + 399$$ So $$7^{9999} \equiv 7^{399} \mod 1000$$ Since $399$ is 1 less than $400$ we can calculate the answer easily. I will show both the long way and the short way.

Long way which works for any power (not all calculations shown):

We divide by two each time to get $$399 = 199+200 \\ 199= 99 + 100 \\ 88= 49 + 50 \\ 49= 24 + 25\\ 25 = 12 + 13 \\ 13 = 6 + 7 \\ 7 = 3+ 4\\ 3 = 1 +2$$ Now (all mod 1000) $$7^1 = 7,~~~ 7^2 = 49\\ 7^3 = 7 \cdot 49 = 343, ~~~7^4 = 49 \cdot 49 = 401\\ 7^6 = 343 \times 343 = 649~~~ 7^7 = 343 \cdot 401 = 543$$ and so on.

You can also find $7^{-1} \mod 1000$ as $143$. So the last 3 digits are 143

• You can use the same idea if you want more digits...$\phi(100) = 100 \times(1/2) \times (4/5)=40$. So $7^{40}$ ends in $01, though finding more digits get to be tedius. – user44197 Jan 1 '14 at 0:51 • hmm... Why the down vote? – user44197 Jan 1 '14 at 0:52 • i do follow this, however if asked for last 3 digits how would i proceed? i understand ϕ(1000)=400 but do not know next steps. thanks – user118512 Jan 1 '14 at 0:53 • Well...9999 = 9600 + 399, so you need$7^{399} \mod 100$. i assume you know how to calculate$7^{399}with just 9 multiplications. If not, ask – user44197 Jan 1 '14 at 0:55 • i followed your first answer and understand 9999 = 9600 + 399 but you lost me at 7^399 mod 100. where am i going from here to find last 1,2 or 3 digits? – user118512 Jan 1 '14 at 1:01 Find the last three digits of $$7^{9999}$$ Solution: By Euler’s theorem $$(7, 10000)$$ are relatively prime therefore $$7 ^ {\phi (1000)} \equiv 1 \pmod {1000}$$ $$\phi (1000) = 1000 (1-1/2) (1-1/5)$$ {$$2$$ & $$5$$ are the only prime divisors of $$1000$$}$$= 400.$$ Hence $$7^{400} \equiv 1 \pmod {1000}$$ Also $$(7^{400}) ^{25}\equiv 1^{25} \pmod {1000}$$ Hence $$7^{10000}\equiv 1 \pmod {1000}\tag 1$$ We know \begin{align} 1001 \equiv 1 &\pmod {1000}\\ \implies 1 \equiv 1001 &\pmod {1000}\\ \implies 1\equiv 7 \times 143 &\pmod {1000}\tag 2\\ \end{align} By $$1$$ and $$2$$ we get $$7^{10000}\equiv 7 \times 143 \pmod {1000}$$ $$7^{9999}\equiv 143 \pmod {1000}$$ Hence the last three digits for $$7^{9999}$$ are $$\bbox[border:2px solid red]{143}$$ Note that7^2=49\equiv 9 \mod 10$, since$9^2=81 \equiv 1 \mod 10$, we have that $$7^4\equiv 1 \mod 10$$ Now notice that$4 \mid 9996$because$4$divides$96$(a number is divisible by$4$iff its last two digits are divisible by$4$). That leaves us with a$7^3$remaining which we know that$7^3\equiv 3 \mod 10$. So that means that $$7^{9999}\equiv 7^3 \equiv 1\cdot 3=3 \mod 10$$ This means the last digit of$7^{9999}$is$3$. • i follow you did 7^9996 * 7^3 but i do not understand what you thinking is behind the first line you wrote: 7^2=49≡9mod10, since 9^2=81≡1mod10, we have that 7^4≡1mod10 – user118512 Jan 1 '14 at 1:15 •$7^4=7^2\cdot 7^2\equiv 9\cdot 9=81\equiv 1 \mod 10$. – mathematics2x2life Jan 1 '14 at 1:17 • ok, a quick check of my underwood dudley book lets me see you are only using last digit, thnks – user118512 Jan 1 '14 at 1:26 • You only asked for the last digit as far as I can tell. If you wanted the last two digits, you would work$\mod 100$, the last three,$\mod 1000$and so forth. – mathematics2x2life Jan 1 '14 at 1:29 calculate the congruence class of$999\bmod\phi(10^n)$(call it$c$). then the last n digits are the last n digits of$7^c$. Use$\phi(10^n)=4(10)^{n-1}$For 1 digit:$999\equiv3\bmod4$so it's$3$for 2 digits$999\equiv39\bmod 40$so its$43$for 3 digits$999\equiv 199 \mod400$so its$143$for more than 3 Euler saves you no time. You can try calculating Charmicael's Lambda which is$2^{n-2}\cdot5^{n-1}$for$n\geq3\$