Results 1 to 4 of 4

Math Help - Congruences: stumped by minus sign

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    8

    Congruences: stumped by minus sign

    This is my first post. I am practicing simple congruence theory to solve divisibility problems.

    For example, to show 13\mid3^{n+2}+4^{2n+1}:
    3^n3^2+(4^2)^n4 \bmod 13 \equiv 3^n9+3^n4 \equiv 3^n(9+4) \equiv 3^n(13) \equiv 3^n(0) \equiv 0 \bmod 13, which is what we set out to prove.

    This works very well for all the problems I've been working on, but there is one with a minus sign that is throwing me off:

    Show: 7\mid5^{2n}+3\cdot2^{5n-2}.

    Any suggestions?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Yep !

    Either you find the multiplicative inverse of 2^2 modulo 7, that is a such that 4a\equiv 1(\bmod 7) (you can see that a=2)
    And hence 2^{-2}=4^{-1} \equiv 2 (\bmod 7)

    Either you use Fermat's little theorem :
    \text{gcd}(2,7)=1 \Rightarrow 2^{7-1}=2^6 \equiv 1 (\bmod 7)

    So
    \begin{aligned}<br />
5^{2n}+3\cdot2^{5n-2} & \equiv 5^{2n}+3\cdot 2^{5n-2} \cdot 5^6 (\bmod 7) \\<br />
&\equiv 5^{2n}+3\cdot 2^{5n+4} (\bmod 7) \end{aligned}
    Last edited by Moo; May 2nd 2009 at 10:48 PM. Reason: BIG typo ><
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    8
    Great. Thanks. So I have to find a workaround to my original method for negatives, in this case, Fermat's little thm.

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

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by glowplug19 View Post
    Great. Thanks. So I have to find a workaround to my original method for negatives, in this case, Fermat's little thm.

    Thank you.
    But remember that Fermat's little theorem works for prime numbers only

    If you had to deal modulo n, where n is not necessarily prime, use Euler's theorem (Euler's theorem - Wikipedia, the free encyclopedia)

    Otherwise, in order to find the multiplicative inverse of a number modulo n (which exists if this number is coprime with n), use trial and error or (better ) the extended Euclidean algorithm (Extended Euclidean algorithm - Wikipedia, the free encyclopedia)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Difference between plus minus and minus plus
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: December 23rd 2011, 04:14 AM
  2. Replies: 4
    Last Post: October 6th 2011, 05:51 PM
  3. Taking a minus sign as a factor.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 5th 2011, 03:10 PM
  4. How to force unary minus (negative sign)?
    Posted in the LaTeX Help Forum
    Replies: 7
    Last Post: July 30th 2009, 05:04 AM
  5. plus/minus in TeX
    Posted in the LaTeX Help Forum
    Replies: 2
    Last Post: May 7th 2009, 03:44 PM

Search Tags


/mathhelpforum @mathhelpforum