Results 1 to 13 of 13
Like Tree1Thanks
  • 1 Post By princeps

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

  1. #1
    Junior Member
    Joined
    Mar 2011
    Posts
    72

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

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

    I do not know how to approach this.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2011
    From
    Crna Gora
    Posts
    420
    Thanks
    64

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

    Quote Originally Posted by math2011 View Post
    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}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2011
    Posts
    72

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

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2011
    From
    Crna Gora
    Posts
    420
    Thanks
    64

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

    Quote Originally Posted by math2011 View Post
    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) ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2011
    Posts
    72

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

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2011
    From
    Crna Gora
    Posts
    420
    Thanks
    64

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

    Quote Originally Posted by math2011 View Post
    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}
    Thanks from math2011
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Mar 2011
    Posts
    72

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

    Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1

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

    Quote Originally Posted by math2011 View Post
    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}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Mar 2011
    Posts
    72

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

    Quote Originally Posted by undefined View Post
    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}?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1

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

    Quote Originally Posted by math2011 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1

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

    Quote Originally Posted by math2011 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Mar 2011
    Posts
    72

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

    Thanks a lot for your explainations!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: February 20th 2013, 09:32 AM
  2. show that 11^33-11^31 is divisible by 5
    Posted in the Algebra Forum
    Replies: 10
    Last Post: August 28th 2010, 08:29 PM
  3. Replies: 1
    Last Post: May 7th 2010, 11:49 PM
  4. [SOLVED] Show that p is divisible by 641?
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: May 22nd 2009, 05:47 AM
  5. Replies: 2
    Last Post: September 22nd 2007, 02:03 PM

Search Tags


/mathhelpforum @mathhelpforum