Nearly a thousand

Number Theory Level 3

Find the last 3 digits of ${7}^{9999}$ .

The answer is 143.

3 solutions

Mathh Mathh
Aug 18, 2014

$\gcd(7,1000)=1$ , thus we can use Euler's theorem .

$7^{9999}\equiv 7^{9999 \mod {\phi(1000)}}\equiv 7^{9999\mod {400}}\equiv 7^{-1}$

Two ways to continue:

$\equiv \frac{1}{7}\equiv \frac{1\cdot 143}{7\cdot 143}\equiv \frac{143}{1001}\equiv \frac{143}{1}\equiv \boxed {143}\pmod{\!1000}$

$\equiv \frac{1}{7}\equiv \frac{1001}{7}\equiv 143\pmod{\! 1000}$

Using fractional notation like above makes sense if and only if the denominator is coprime to the modulus.

If the fraction makes sense, its denominator can always be reduced mod the modulus. In this case note $\gcd(7,1000)=\gcd(143,1000)=1$ , so everything makes sense and can be reduced.

In simpler terms: the second method was:

$7x\equiv 7\cdot 7^{9999}\equiv 7^{10000\pmod{\! 400}}\equiv 7^0$

$\equiv 1\equiv 1001\stackrel{:7}\iff x\equiv 143\pmod{\! 1000}$

The first method was:

$7x\equiv \cdots\equiv 1\stackrel{\cdot 143}\iff 1001x\equiv x\equiv 143\pmod{\! 1000}$

${7}^{\phi(1000)}$ = 1 mod 1000

${7}^{400}$ = 1 mod 1000

${7}^{10000}$ = 1 mod 1000

${7}^{9999}$ = 1001/7 mod 1000

${7}^{9999}$ = 143 mod 1000

Although you have done the same, but I am just sharing it in a 'simple' form, I think.

Hey, @mathh mathh do you know what to do when (10^n + 1) is a prime or not divisible by the number(here, 7)? I read in A. Engel's book about it but I didn't get it.

Kartik Sharma - 6 years, 9 months ago

You just add $1000$ 's, like $1001, 2001, 3001$ , etc., until the number is divisible by $7$ .

My method is simple given you have in mind that the denominator can't be simplified when it is not coprime to the modulus. This is the only rule, but isn't difficult to forget when working. In our example we couldn't scale anything by an even number or a multiple of $5$ .

mathh mathh - 6 years, 9 months ago

Thank You!

Kartik Sharma - 6 years, 9 months ago

@Kartik Sharma – @Kartik Sharma In case adding $1000$ 's doesn't help (this can easily happen when all the numbers are big; when they're small, because of the law of small numbers we have that they're often easily simplifiable), we can usually use the Extended Euclidean algorithm, which will almost always help. See my response to Rishabh Jain.

mathh mathh - 6 years, 9 months ago

I didnt understand the last few parts. :/

Jayakumar Krishnan - 6 years, 9 months ago

If the text under the line is not fully understandable, then sorry - I wanted to edit it to make it more clear, but brilliant doesn't seem to let me edit it.

Anyway, what it's saying is just that you must have the denominator and the modulus coprime if you want to reduce the denominator using the modulus. That's the only restriction if you're working with fractions.

E.g.

$\frac{1}{7}\stackrel{\times 3}\equiv\frac{3}{21}\equiv \frac{3}{1}\equiv \boxed{3}\pmod {10}$

But you couldn't have scaled it by $2$ , since $\gcd(2,10)=2\neq 1$ .

mathh mathh - 6 years, 9 months ago

what should we do if it is ${7}^{9996}$

Rishabh Jain - 6 years, 9 months ago

In this case, as you can see, we'd need to find $\frac{1}{7^4}\equiv \frac{1}{401}\pmod {1000}$

Now, having modulus as big as $1000$ , solving this without using the Extended Euclidean Algorithm would be quite tough. In this problem's case, we were very lucky that $7\mid 1001$ , but we don't really, in your case, have $7^4\mid 1001$ or $2001$ or anything similar, so it's quite tough.

To find the modular multiplicative inverse of $401$ modulo $1000$ (which exists since $\gcd(1000,401)=1$ ), we can use the Extended Euclidean Algorithm.

$1000(160)+401(-399)=1$

Hence $\frac{1}{401}\equiv -399\equiv \boxed{601}\pmod {1000}$ .

The Extended Euclidean Algorithm will find you the inverse of any number modulo another that is coprime to it (if not coprime, the inverse does not exist. Always scale the fractions by a number coprime to the modulus).

mathh mathh - 6 years, 9 months ago

Very nicely explained mathh mathh .. Loved ur solution.. :)

Ayush Garg - 6 years, 2 months ago

its my doubt since a long time that how can we calculate the numbers equal to or less than N which are co-prime to N plz can u explain @mathh mathh

sakshi rathore - 5 years, 11 months ago

@sakshi rathore Please ask, if you have any questions.

mathh mathh - 5 years, 11 months ago

our teacher told us that to find the last three digits we have to know the binomial expansion of it is it really necessary ??not any other method @mathh mathh

sakshi rathore - 5 years, 11 months ago

@Sakshi Rathore – @sakshi rathore Well, above answer found the last three digits of $7^{9999}$ without using Binomial theorem.

There are many methods of finding the last three digits of $a^b$ . One of them is using Euler's theorem (or the stronger Carmichael function ), like I did above. Read the end of my answer for a simplified solution.

Sometimes Euler's theorem or Carmichael function is enough, like it was in my answer. If not, then after reducing, you can use Binomial theorem, especially in the following cases:

1) If $a=10k\pm 1$ , then

$a^b\equiv (\pm 1+10k)^b\equiv (\pm 1)^b+\binom{b}{1}(\pm 1)(10k)+\binom{b}{2}(\pm 1)(100k)\,\pmod{\! 1000}$

2) If (1) can't be used, then if $a=5k\pm 1$ , then

$a^b\equiv (\pm 1+5k)^{b}\equiv (\pm 1)^b+\binom{b}{1}(\pm 1)(5k)+\binom{b}{2}(\pm 1)(25k)\pmod{\! 125}$

$a^b\bmod 8$ is easy to calculate. Then use Chinese Remainder theorem .

Never forget you can use Chinese Remainder theorem, Euler's theorem. It makes some problems extremely simple. E.g., $126^{891}\equiv 1\,\pmod{\! 125}$ and $126^{891}\equiv 0\,\pmod{\! 8}$ , so by Chinese Remainder theorem the last three digits of $126^{891}$ are $376$ . Another example: $453^{101^{99}}\equiv 453^{101^{99}\pmod{\! 100}}\equiv 453\pmod{\! 125}$ and $453^{101^{99}}\equiv 453^{101^{99}\pmod{\! 4}}\equiv 453\pmod{\! 8}$ , so $453^{101^{99}}\equiv 453\pmod{\! 1000}$ . So you don't always need Binomial Theorem - never forget Chinese Remainder theorem, Euler's theorem (sometimes Carmichael function).

mathh mathh - 5 years, 11 months ago

@Mathh Mathh – oh thank you sir for explaining so well

sakshi rathore - 5 years, 11 months ago

@sakshi rathore I think you want to find $\phi(1000)$ ?

Let's calculate $\phi(n)$ . Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ (remember Fundamental theorem of arithmetic ).

Below formula can be proved:

$\phi(n)=\phi\left(p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\right) =\left(p_1^{\alpha_1}-p_1^{\alpha_1-1}\right)\cdots \left(p_k^{\alpha_k}-p_k^{\alpha_k-1}\right)$

Another formula (above formula written in a different way):

$\phi\left(p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\right) =n\left(1-\frac{1}{p_1}\right)\cdots \left(1-\frac{1}{p_k}\right)$

So you can just use the formulas instead of searching for all the numbers $\le 1000$ coprime to $1000$ .

$\phi(1000)=\phi\left(2^3\cdot 5^3\right)=\left(2^3-2^2\right)\left(5^3-5^2\right)=400$

So there are $400$ numbers less than or equal to $1000$ that are coprime to $1000$ .

If you understand Chinese Remainder Theorem, the proof of the formulas is very simple - see Wikipedia .

mathh mathh - 5 years, 11 months ago

Saket Sharma
Sep 19, 2014

Just observation!

Consider 7^{N}.

Unit place digit has a cycle of 4: 7, 9, 3, 1, 7, 9, 3, 1, ...

Tens place digit has a cycle of 4: 0, 4, 4, 0, 0, 4, 4, 0, ...

Hundredth place digit has a cycle of 20:

0, 0, 3, 4, 8, 6, 5, 8, 6, 2, 7, 2, 4, 8, 9, 6, 2, 4, 1, 0,

0, 0, 3, 4, 8, 6, ...

Now, 100 or 1000 or 10000 etc. are all divisible by 20 (and therfore by 4 as well).

Hence, for each of N = 99, 999, 9999, 99999, etc

7^{N} ends in 143 .

Girija Lenka
Mar 12, 2015

First of all, 7 and 10 are relatively prime, so Euler's theorem applies. You are essentially wanting 7^9999 modulo 1000. Now, the totient function of 1000=2^3 5^3 is (2-1) 2^2 (5-1)^5^2, which is 400. Hence, 7^400=1 mod 1000. So the question is what 9999 is modulo 400. Clearly, it is -1. So what you really want is 7^(-1) mod 1000. In other words, you want an x so that 7x=1 mod 1000. But, it turns out that 7 11 13=1001 is 1 mod 1000, so x=11*13=143.

Thus, the last 3 digits of 7^9999 are 143.

Nearly a thousand

The answer is 143.

3 solutions

0 pending reports