1
$\begingroup$

$11^{10} \equiv 1 \pmod{100}$

I tried to solve by using euler's theorem, But I got stuck.

$\gcd(11, 100) = 1$

$11^{φ(100)} \equiv 1 \pmod{100}$

$11^{40} \equiv 1 \pmod{100}$

I don't know how to go on as $11^{40}$ is bigger than $11^{10}$

$\endgroup$
4
  • 2
    $\begingroup$ Binomial theorem? $\endgroup$ – Angina Seng Aug 28 '17 at 18:22
  • $\begingroup$ I would suggest multiplying by hand $11 \times 11$ reducing modulo $100$ as you go, and see what transpires. Repeated squaring can be quicker for computing large powers. You could also try a binomial expansion of $(1+10)^{10}$. But try something and look out for helpful patterns. $\endgroup$ – Mark Bennet Aug 28 '17 at 18:23
  • $\begingroup$ @MarkBennet I don't know this binomial theorem, this example can't be solved by euler's theorem ? $\endgroup$ – Goun2 Aug 28 '17 at 18:24
  • 1
    $\begingroup$ Even if you do not use it for this question, the binomial theorem is a tremendously valuable thing to know. I recommend learning it. $\endgroup$ – David K Aug 28 '17 at 18:34
8
$\begingroup$

Hint:

$$(1+10)^n\equiv1+\binom n110^1\pmod{10^2}$$ for positive integer $n$

$\endgroup$
10
  • 1
    $\begingroup$ I didn't understand :/, what do you mean with this ? $\endgroup$ – Goun2 Aug 28 '17 at 18:30
  • $\begingroup$ Why doesn't the euler's theorem work for this case ? (11,100) are relatevely prime, it should work. $\endgroup$ – Goun2 Aug 28 '17 at 18:31
  • $\begingroup$ @hjx He used the binomial theorem. $\endgroup$ – user236182 Aug 28 '17 at 18:33
  • 3
    $\begingroup$ The theorem does work, bit it just isn't useful for this particular problem. $\endgroup$ – Batominovski Aug 28 '17 at 18:33
  • 1
    $\begingroup$ @hjx Not knowing the Binomial Theorem is not an excuse for not trying to search for it, understand what it says, and find out about the proof, especially, when this theorem is one of the most fundamental theorems in mathematics that everybody should have learned at some point in their life. $\endgroup$ – Batominovski Aug 28 '17 at 20:09
7
$\begingroup$

Well..., you got $11^{40} \equiv 1 \pmod{100}\Rightarrow (11^{10}-1)(11^{10}+1)(11^{20}+1)\equiv 0 \pmod{100}$

Now it is easy to see that $(11^{10}+1)$ and $(11^{20}+1)$ end with $2$. Then $(11^{10}-1)\equiv 0 \pmod{25}$

Again $11^{2} \equiv 1 \pmod{4}\Rightarrow 11^{10} \equiv 1 \pmod{4}$

Since $\gcd(25,4)=1$, we will have $11^{10} \equiv 1 \pmod{100}\space\space\space\space\space\blacksquare$

$\endgroup$
4
$\begingroup$

$11^{10}-1$

$=(1+10)^{10}-1$

$=(1+\binom{10}{1}10+\binom{10}{2}10^2+...+10^{10})-1$

$=\binom{10}{1}10+\binom{10}{2}10^2+...+10^{10}$

is divisible by $100$.

$\endgroup$
2
$\begingroup$

Alternatively: $$11^{10}-1=(11^5-1)(11^5+1)=(11-1)(11^4+11^3+11^2+11+1)(11^5+1)=$$ $$10\cdot (...5)(...2)=...00.$$

$\endgroup$
2
$\begingroup$

Here is an indirect proof

Note that $\varphi (4) = 2$ and $\varphi (25) = 20$ so that if $r$ has no factor in common with $100$ we have $r^{20}\equiv 1 \bmod 4, \text{ and } \bmod 25 \text { hence also } \bmod 100$.

Note also that $6^2=36 \equiv 11 \bmod 25$

We have $$11^{10}=(11^2)^5 \equiv 1\bmod 4$$ and also $$11^{10}\equiv 6^{20}\equiv 1 \bmod 25$$ so that $$11^{10}\equiv 1 \bmod 100$$

Note that $11$ is not a square modulo $4$ or $100$, but the reduction of exponent by a factor of $2$ (which doesn't apply to the factor $4$ - with $\varphi (4)=2$ needing no reduction - $2$ is still a factor of the target exponent $10$) suggests looking for a square root modulo $25$.

$\endgroup$
2
$\begingroup$

You can use the binomial theorem if you want, but here it is a silly solution:

$11^2=21\operatorname{mod}100$, thus $11^{10}=(11^2)^5=21^5\operatorname{mod}100$.

If you compute $21^5=4.084.101=1\operatorname{mod}100$.

$\endgroup$
0
$\begingroup$

$$\qquad{11^2\equiv 121\equiv 21\mod 100\\\\ (11^2)\times 11\equiv 231\equiv 31\mod 100\\ (11^4)\equiv 31\times 11\equiv 341\equiv 41\mod 100\\ (11^5)\equiv 41\times 11\equiv 451\equiv 51\mod 100\\ (11^6)\equiv 51\times 11\equiv 61\mod 100\\ (11^7)\equiv 61\times 11\equiv 71\mod 100\\ (11^8)\equiv 71\times 11\equiv 81\mod 100\\ (11^9)\equiv 81\times 11\equiv 91\mod 100\\ (11^{10})\equiv 91\times 11\equiv 1001\equiv 1\mod 100\\}$$

$\endgroup$
0

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.