# Show that 98^76543 + 21 is not divisible by 11.

Printable View

• Mar 16th 2012, 11:30 PM
math2011
Show that 98^76543 + 21 is not divisible by 11.
Show that $\displaystyle 98^{76543} + 21$ is not divisible by $\displaystyle 11$.

I do not know how to approach this.
• Mar 17th 2012, 12:03 AM
princeps
Re: Show that 98^76543 + 21 is not divisible by 11.
Quote:

Originally Posted by math2011
Show that $\displaystyle 98^{76543} + 21$ is not divisible by $\displaystyle 11$.

I do not know how to approach this.

Hint :

$\displaystyle \begin{cases}98^n-1 \equiv 0 \pmod {11}, & \text{if }n\text{ is even} \\98^n-1 \equiv 9 \pmod{11}, & \text{if }n\text{ is odd}\end{cases}$
• Mar 17th 2012, 03:08 AM
math2011
Re: Show that 98^76543 + 21 is not divisible by 11.
Since $\displaystyle n = 76543$ is odd, so $\displaystyle 98^{76543} - 1 \equiv 9 (mod 11)$. We also have $\displaystyle 20 \equiv 9 (mod 11)$. Hence $\displaystyle 98^{76543} - 1 - 20 \equiv 9 - 9 (mod 11)$ or $\displaystyle 98^{76543} - 21 \equiv 0 (mod 11)$. Doesn't this mean that $\displaystyle 98^{76543} - 21$ is divisible by $\displaystyle 11$?

How would you work out the congruence relations you stated by yourself say in exam conditions?
• Mar 17th 2012, 03:32 AM
princeps
Re: Show that 98^76543 + 21 is not divisible by 11.
Quote:

Originally Posted by math2011
Since $\displaystyle n = 76543$ is odd, so $\displaystyle 98^{76543} - 1 \equiv 9 (mod 11)$. We also have $\displaystyle 20 \equiv 9 (mod 11)$. Hence $\displaystyle 98^{76543} - 1 - 20 \equiv 9 - 9 (mod 11)$ or $\displaystyle 98^{76543} - 21 \equiv 0 (mod 11)$. Doesn't this mean that $\displaystyle 98^{76543} - 21$ is divisible by $\displaystyle 11$?

How would you work out the congruence relations you stated by yourself say in exam conditions?

You are correct but your question was :

$\displaystyle \text{Does}~11 \mid \left(98^{76543}+21\right) ?$
• Mar 17th 2012, 04:18 AM
math2011
Re: Show that 98^76543 + 21 is not divisible by 11.
Thanks! Sometimes I get really confused.

So $\displaystyle 22 \equiv 0 (\mod 11)$ and add this to your congruence we get $\displaystyle 98^{76543} - 1 + 22 \equiv 9 + 0 (\mod 11)$ which is $\displaystyle 98^{76543} + 21 \equiv 9 (\mod 11)$.

But still, how do you know that $\displaystyle 98^{n} -1 \equiv 9 (\mod 11)$ when $\displaystyle n$ is odd?
• Mar 17th 2012, 04:45 AM
princeps
Re: Show that 98^76543 + 21 is not divisible by 11.
Quote:

Originally Posted by math2011
Thanks! Sometimes I get really confused.

So $\displaystyle 22 \equiv 0 (\mod 11)$ and add this to your congruence we get $\displaystyle 98^{76543} - 1 + 22 \equiv 9 + 0 (\mod 11)$ which is $\displaystyle 98^{76543} + 21 \equiv 9 (\mod 11)$.

But still, how do you know that $\displaystyle 98^{n} -1 \equiv 9 (\mod 11)$ when $\displaystyle n$ is odd?

$\displaystyle 98^n-1=97 \cdot \displaystyle \sum_{i=0}^{n-1} 98^i$

Note that :

$\displaystyle 97 \equiv 9 \pmod {11} ~\text{and}~\displaystyle \sum_{i=0}^{n-1} 98^i \equiv 1 \pmod {11}$

hence:

$\displaystyle 98^n-1 \equiv 9 \pmod {11}$
• Mar 17th 2012, 06:06 AM
math2011
Re: Show that 98^76543 + 21 is not divisible by 11.
Thank you very much.
• Mar 18th 2012, 06:10 PM
undefined
Re: Show that 98^76543 + 21 is not divisible by 11.
Quote:

Originally Posted by math2011
But still, how do you know that $\displaystyle 98^{n} -1 \equiv 9 (\mod 11)$ when $\displaystyle n$ is odd?

Also:

$\displaystyle 98 \equiv -1 \pmod{11}$

So the entire proof can be written as a one-liner:

$\displaystyle 98^{76543}+21 \equiv (-1)^{76543}+10 \equiv 9 \pmod{11}$
• Mar 19th 2012, 01:49 AM
math2011
Re: Show that 98^76543 + 21 is not divisible by 11.
Quote:

Originally Posted by undefined
Also:

$\displaystyle 98 \equiv -1 \pmod{11}$

So the entire proof can be written as a one-liner:

$\displaystyle 98^{76543}+21 \equiv (-1)^{76543}+10 \equiv 9 \pmod{11}$

Thanks, this is brilliant. Did you observer that $\displaystyle 98 \equiv -1 (\mod 11)$ and then work on this congruence like
$\displaystyle 98 \equiv -1 \pmod{11}$
$\displaystyle 98^{76543} \equiv (-1)^{76543} \pmod{11}$
$\displaystyle 98^{76543} \equiv -1 \pmod{11}$
$\displaystyle 98^{76543} + 21 \equiv -1 + 21 \pmod{11}$
$\displaystyle 98^{76543} + 21 \equiv 20 \pmod{11}$
$\displaystyle 98^{76543} + 21 \equiv 9 \pmod{11}$?
• Mar 19th 2012, 05:59 AM
undefined
Re: Show that 98^76543 + 21 is not divisible by 11.
Quote:

Originally Posted by math2011
Thanks, this is brilliant. Did you observer that $\displaystyle 98 \equiv -1 (\mod 11)$ and then work on this congruence like
$\displaystyle 98 \equiv -1 \pmod{11}$
$\displaystyle 98^{76543} \equiv (-1)^{76543} \pmod{11}$
$\displaystyle 98^{76543} \equiv -1 \pmod{11}$
$\displaystyle 98^{76543} + 21 \equiv -1 + 21 \pmod{11}$
$\displaystyle 98^{76543} + 21 \equiv 20 \pmod{11}$
$\displaystyle 98^{76543} + 21 \equiv 9 \pmod{11}$?

Well, I didn't do it in exactly that order, but that's equivalent. The steps can be written for example like this:

$\displaystyle 98^{76543} \equiv (-1)^{76543} \equiv -1 \pmod{11}$

$\displaystyle 21 \equiv 10 \pmod{11}$

$\displaystyle 98^{76543}+21 \equiv -1 + 10 \equiv 9 \pmod{11}$

But anyone reasonably familiar with congruences should be able to follow the one-liner I wrote above without any intermediate steps.

In general, in the context of an exam, you may be presented with $\displaystyle a^b \pmod{n}$ such that gcd(a,n)=1 and be expected to recognise that Euler's theorem applies. But if $\displaystyle a$ is congruent to 1, 0, or -1 (mod n), then you should definitely take advantage of that to make calculations very easy. And there are other related topics you can learn about if you are interested in such things.
• Mar 20th 2012, 02:37 AM
math2011
Re: Show that 98^76543 + 21 is not divisible by 11.
Thanks for the advice. We haven't done Totient functions or Euler's theorem yet. What related topics are you referring to? Are they shortcuts for solving congruence problems or more advanced topics?
• Mar 20th 2012, 06:10 AM
undefined
Re: Show that 98^76543 + 21 is not divisible by 11.
Quote:

Originally Posted by math2011
Thanks for the advice. We haven't done Totient functions or Euler's theorem yet. What related topics are you referring to? Are they shortcuts for solving congruence problems or more advanced topics?

A little of both, I guess. The Chinese Remainder Theorem can be used if gcd(a,n)>1, and (mainly discussed in a computer science context) there's an algorithm for fast modular exponentiation by repeated squaring. Using such concepts you could compute things like the common residue of $\displaystyle a^{b^{c^d}} \pmod{n}$ for nontrivial a,b,c,d,n. (And the numbers can get very large very quickly; for example, $\displaystyle 2^{2^{3^3}}$ has 40403563 digits.) You probably won't get something like that on a test, but nevertheless it's possible that having extra knowledge might provide a shortcut for certain problems.
• Mar 21st 2012, 11:32 PM
math2011
Re: Show that 98^76543 + 21 is not divisible by 11.
Thanks a lot for your explainations!