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

**math2011** · March 16th 2012, 11:30 PM

Show that $98^{76543} + 21$ is not divisible by $11$ .

I do not know how to approach this.

**princeps** · March 17th 2012, 12:03 AM

Originally Posted by math2011

Show that $98^{76543} + 21$ is not divisible by $11$ .

I do not know how to approach this.

Hint :

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

**math2011** · March 17th 2012, 03:08 AM

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

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

**princeps** · March 17th 2012, 03:32 AM

Originally Posted by math2011

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

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

You are correct but your question was :

$\text{Does}~11 \mid \left(98^{76543}+21\right) ?$

**math2011** · March 17th 2012, 04:18 AM

Thanks! Sometimes I get really confused.

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

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

**princeps** · March 17th 2012, 04:45 AM

Originally Posted by math2011

Thanks! Sometimes I get really confused.

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

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

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

Note that :

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

hence:

$98^n-1 \equiv 9 \pmod {11}$

**math2011** · March 17th 2012, 06:06 AM

Thank you very much.

**undefined** · March 18th 2012, 06:10 PM

Originally Posted by math2011

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

Also:

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

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

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

**math2011** · March 19th 2012, 01:49 AM

Originally Posted by undefined

Also:

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

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

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

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

**undefined** · March 19th 2012, 05:59 AM

Originally Posted by math2011

Thanks, this is brilliant. Did you observer that $98 \equiv -1 (\mod 11)$ and then work on this congruence like
$98 \equiv -1 \pmod{11}$
$98^{76543} \equiv (-1)^{76543} \pmod{11}$
$98^{76543} \equiv -1 \pmod{11}$
$98^{76543} + 21 \equiv -1 + 21 \pmod{11}$
$98^{76543} + 21 \equiv 20 \pmod{11}$
$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:

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

$21 \equiv 10 \pmod{11}$

$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 $a^b \pmod{n}$ such that gcd(a,n)=1 and be expected to recognise that Euler's theorem applies. But if $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.

**math2011** · March 20th 2012, 02:37 AM

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?

**undefined** · March 20th 2012, 06:10 AM

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 $a^{b^{c^d}} \pmod{n}$ for nontrivial a,b,c,d,n. (And the numbers can get very large very quickly; for example, $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.

**math2011** · March 21st 2012, 11:32 PM

Thanks a lot for your explainations!

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

LinkBack

Thread Tools

Display

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

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

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

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

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

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

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

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

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

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

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

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

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

Similar Math Help Forum Discussions

Show that pos int divisible by 3 iff sum of digits divisible by 3

show that 11^33-11^31 is divisible by 5

Prove that if x's square is divisible by a, then x is also divisible by a

[SOLVED] Show that p is divisible by 641?

Show that it is divisible by 7 for all positive integers...

Search Tags