2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How many final digits do you seek? $\endgroup$ – Bill Dubuque Jan 1 '14 at 0:45
  • $\begingroup$ 1 - 3 is what i would like to be able to solve $\endgroup$ – user118512 Jan 1 '14 at 0:54
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jan 1 '14 at 0:57
  • $\begingroup$ ex: i can find ϕ(1000)=400, but do not know ad-hoc steps to follow after that? thks $\endgroup$ – user118512 Jan 1 '14 at 1:02
  • $\begingroup$ 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). $\endgroup$ – Bill Dubuque Jan 1 '14 at 1:04
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user44197 Jan 1 '14 at 0:51
  • $\begingroup$ hmm... Why the down vote? $\endgroup$ – user44197 Jan 1 '14 at 0:52
  • $\begingroup$ 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 $\endgroup$ – user118512 Jan 1 '14 at 0:53
  • $\begingroup$ 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 $\endgroup$ – user44197 Jan 1 '14 at 0:55
  • $\begingroup$ 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? $\endgroup$ – user118512 Jan 1 '14 at 1:01
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

Note that $7^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$.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user118512 Jan 1 '14 at 1:15
  • $\begingroup$ $7^4=7^2\cdot 7^2\equiv 9\cdot 9=81\equiv 1 \mod 10$. $\endgroup$ – mathematics2x2life Jan 1 '14 at 1:17
  • $\begingroup$ ok, a quick check of my underwood dudley book lets me see you are only using last digit, thnks $\endgroup$ – user118512 Jan 1 '14 at 1:26
  • $\begingroup$ 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. $\endgroup$ – mathematics2x2life Jan 1 '14 at 1:29
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.