1
$\begingroup$

Decide whether each of the following is true or false without using a calculator: The problem is:

$$11^{99}\equiv 1\pmod{5}$$

Now I know I can break the $11$ into $(10+1)^{99}$ and maybe rewrite it as $(10+1)^{98}\times (10+1)$ and then realize that $10+1\equiv 1\pmod{5}$ and then just deal with $(10+1)^{98}$ but that means I have to do this $97$ times until at the end I have $10+1\equiv 1\pmod 5$ but I feel like this is a very stupid way to look at it. Is there a little trick of sorts that I can use on problems like this when the exponents are huge?

$\endgroup$
  • 4
    $\begingroup$ Hint: $11\equiv 1\pmod{5}$. $\endgroup$ – vadim123 Mar 25 '15 at 17:44
  • 3
    $\begingroup$ After eight questions asked I think it is time to learn how to properly write mathematics in this site: meta.math.stackexchange.com/questions/5020/… $\endgroup$ – Timbuc Mar 25 '15 at 17:44
  • 2
    $\begingroup$ @vadim123 I think your hint is the best answer. $\endgroup$ – David K Mar 25 '15 at 18:04
4
$\begingroup$

Notice below $$11^{99} - 1^{99} = (11-1)(11^{98}+11^{97}+\cdots+1) =10M$$

Since $11\equiv 1\pmod{5}$, we have $11^k\equiv 1^k \pmod{5}$

In general : $$a\equiv b\pmod{n} \implies a^k\equiv b^k \pmod{n}$$

$\endgroup$
1
$\begingroup$

Hint: Euler's Theorem. For the case of modulo prime, use the corollary of it, Fermat's Little Theorem

$\endgroup$
  • $\begingroup$ Not necessary. $11$ raised to the power of itself any number of times ends with $1$, take away, $1$ from it, it ends with $0$, so it's divisible by $5$ $\endgroup$ – GohP.iHan Apr 21 '15 at 4:32
  • $\begingroup$ @GohP.iHan, the OP further asked if there's any method in general that'll allow him to approach problems like this. That's precisely the reason I mentioned these theorems in my answer. $\endgroup$ – Prasun Biswas Apr 21 '15 at 5:33
1
$\begingroup$

There are many ways to approach this.

One way is to note that for all $n$: if $\gcd(a,n) = 1$:

$a^{\phi(n)} = 1$ (mod $n$). This is known as Euler's Theorem.

Here, we have $a = 11, n = 5$, and $\phi(5) = 4$, so we have:

$11^{99} = (11^{96})(11^3) = (11^{4})^{24}(11^3) = (1^{24})(11^3) = 11^3$ (mod $5$).

Then it is easy to see:

$11^3 = (5\cdot 20 + 1)(5 \cdot 2 + 1) = 5\cdot (200 + 22) + 1$ so that:

$11^3 = 1$ (mod $5$).

It is also easy to prove by induction on $k$, that $11 = 1$ (mod $5$) $\implies 11^k = 1$ (mod $5$).

Certainly this is self-evident for $k = 1$, since $11 = 2\cdot 5 + 1$.

Suppose now that $11^{k-1} = 1$ (mod $5$). This means there is some integer $t$, so that:

$11^{k-1} = 5t + 1$.

Then $11^k = (11^{k-1})(11) = (5t + 1)(10 + 1) = 5\cdot(10t + t + 2) + 1$, so taking:

$t' = 10t + t + 2$, we see $11^k = 5t' + 1$, that is: $11^k = 1$ (mod $5$).

Now this holds for ANY natural number $k$, so in particular, $k = 99$.

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