Page 1 of 2 12 LastLast
Results 1 to 15 of 18
Like Tree13Thanks

Math Help - Modular arithmetic

  1. #1
    Member
    Joined
    Nov 2013
    From
    Australia
    Posts
    176
    Thanks
    36

    Modular arithmetic

    1/192 = k mod7

    I ran this through Wolfram Alpha and got the answer k=5

    I assume that this is because

    (192 * 5)/7 has a remainder of 1 (is this correct?)

    Is there a good way of finding the 5 manually?

    Thankyou.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2009
    Posts
    652
    Thanks
    128

    Re: Modular arithmetic

    You're certainly covering some ground Melody !

    I don't ever remember mixing reciprocals with modular arithmetic before, so this is something of a first for me.
    (Hope it's OK.)

    192 \equiv 3(\text{mod} 7), so multiplying this with your equation, we have 1 \equiv 3k(\text{mod} 7), which implies that 1-3k=7n for some integer n.

    The smallest (positive) integer value for k satisfying this is k=5.
    Thanks from Melody2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121

    Re: Modular arithmetic

    Yes. 1/a= b is the same as ab= 1 in any commutative algebraic system.

    As for finding 1/192 (mod 7), the first thing you should do is note that 7 divides into 192 27 times with remainder 3, so 192= 3 (mod 7). Finding 1/192 (mod 7) is the same as finding 1/3 (mod 7) which is the same as saying that if x= 1/3 (mod 7) then 3x= 1 (mod 7) and you can just check: 1*3= 3, 2*3= 6, 3*3= 9= 2 (mod 7), 3*4= 12= 5 (mod 7), 3*5= 15= 1 (mod 7), and 3*6= 18= 4 (mod 7). That is, since 3*5= 1 (mod 7), 5= 1/3 (mod 7)= 1/192 (mod 7).

    A more general way of solving "x= 1/b (mod a)" is to use Diophantine equations. Of course, "192x= 1 (mod 7)" means that 192x= 1+ 7y for some integer y. So solving 192x= 1 (mod 7) is the same as solving the Diophantine equation 192x- 7y= 1. There are several different methods to do that. Here's what I would do:

    7 divides into 192 27 times with remainder 3. That is, 192- 27(7)= 3.
    3 divides into 7 twice with remainder 1. That is, 7- 2(3)= 1.

    Replacing the "3" in "7- 2(3)= 1" with "192- 27(7)" gives 7- 2(192- 27(7))= 7- 2(192)+ 54(7)= 55(7)- 2(192)= (-2)(192)- (-55)(7)= 1.

    That is, one solution to 192x- 7y= 1 is x= -2, y= -55.

    So x= -2 (mod 7) which is the same as x= -2+ 7= 5 (mod 7).
    Last edited by HallsofIvy; January 14th 2014 at 05:54 AM.
    Thanks from Melody2 and topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91

    Re: Modular arithmetic

    Quote Originally Posted by Melody2 View Post
    1/192 = k mod7
    It’s the linear congruence 192k=1(mod7) which has the unique (7 is prime) solution:
    k=5(mod7)

    k=5 by trial and error with a calculator*. The other solutions are k= 5+7, k=5+2x7, k=5+3x7,…

    Ex: 192(5+2x7)-1=521x7

    *192k-1=7p: try 192k-1, k=1,2,3…, and divide by 7 till you get an integer.
    Thanks from Melody2
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2013
    From
    Australia
    Posts
    176
    Thanks
    36

    Re: Modular arithmetic

    Thankyou, I got a lot from each of these answers. I am really grateful.
    I am still pondering the second half of Hallsofivy's answer, I might be back, I hope that's ok.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2013
    From
    Australia
    Posts
    176
    Thanks
    36

    Re: Modular arithmetic

    A more general way of solving "x= 1/b (mod a)" is to use Diophantine equations. Of course, "192x= 1 (mod 7)" means that 192x= 1+ 7y for some integer y. So solving 192x= 1 (mod 7) is the same as solving the Diophantine equation 192x- 7y= 1. There are several different methods to do that. Here's what I would do:

    7 divides into 192 27 times with remainder 3. That is, 192- 27(7)= 3.
    3 divides into 7 twice with remainder 1. That is, 7- 2(3)= 1.

    Replacing the "3" in "7- 2(3)= 1" with "192- 27(7)" gives 7- 2(192- 27(7))= 7- 2(192)+ 54(7)= 55(7)- 2(192)= (-2)(192)- (-55)(7)= 1.

    That is, one solution to 192x- 7y= 1 is x= -2, y= -55.

    So x= -2 (mod 7) which is the same as x= -2+ 7= 5 (mod 7).


    Hello again,
    My question concerns the Diophantine equation solution.
    I can follow HallsofIvy's solution, at least at a very superficial level, but, firstly, I don't understand why it is more general and, secondly, I can't work out how to apply it to other problems.

    I am considering
    5/286 = x (mod7)
    5=286x (mod7)
    286/7 = 40 and 6/7 therefore 286 mod7 = 6
    6x=5 mod7
    6x = 5, 12,19 etc
    x=2+7N where N is any integer
    ok that's the easy way done with.
    --------------------------------------------------
    now for the other way.
    286x = 7y+5 for some y in the set of integers
    286x-7y=5

    286/7 = 40 +6/7
    286=40(7)+6
    286-40(7)=6 (1)

    7/6 = 1 +1/6
    7 = 6(1) +1
    Sub in (1)
    7 = 286-40(7) +1
    -286+41(7) = 1
    286(-1)-7(-41) =1
    how does this help???
    I'm obviously doing it wrong.

    So my 2 questions are
    What am I doing wrong and why is this way more general?
    Thank you for your patience and your time.
    Last edited by Melody2; January 17th 2014 at 05:34 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,546
    Thanks
    539

    Re: Modular arithmetic

    Hello, Melody2!

    \frac{1}{192} \:\equiv\:k \text{ (mod 7)}

    We have: . 192k \,\equiv\,1 \text{ (mod 7)}

    Then: . 192k \:=\:1 + 7a\:\text{ for some integer }a.

    Solve for a\!:\;a \:=\:\frac{192k-1}{7} \quad\Rightarrow\quad a \:=\:27k + \frac{3k-1}{7}

    Since a is an integer, (3k-1) must be a multiple of 7.
    The first time this happens is: k = 5.

    Therefore: . \frac{1}{192} \,\equiv\,5\text{ (mod 7)}
    Thanks from Melody2 and topsquark
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Nov 2013
    From
    Australia
    Posts
    176
    Thanks
    36

    Re: Modular arithmetic

    Thanks Soroban,
    I really like this setting out but it has lead me to more questions.

    Can k ever have a fractional answer for a question similar to this?
    "Since a is an integer, (3k-1) must be a multiple of 7." This statement of yours is only true if k is an integer.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91

    Re: Modular arithmetic

    Modular arithmetic deals with integers. You are looking for k an integer. But that's not why I called (old joke).

    HallsofIvy’s procedure, I think (I generally don’t pay much attention to procedures or formulas without an explanation, but I finally recalled):

    Given: ax=b(modm) & (a,m)=1, (a,m) is gcd
    From Euclidean algorithm: (a,m)=sa+tm=1*
    multiply by b
    b=(bs)a+(bt)m → (bt)m=b-(bs)a so (bs) is a sol.
    if m is prime it is the only solution modm. If (a,m)>1, there are other sols.

    *Euclidean (division) algorithm: a=qm+r, 0 ≤ r < m
    Procedure to get (a,m)=sa+tm best illustrated by example (57,21):

    57=2(21) + 15,…….. (57,21)=(21,15)
    21=1(15)+6,………... (21,15)=(15,6)
    15=2(6)+3,……...…….(15,6)=(6,3)
    6=2(3),………….....……(6,3)=3
    so (57,21)=3

    To express (57,21)=3 in the form s(57)+t(21)
    15=57-2(21)
    6=21-15=21-[57-2(21)]= -1(57)+3(21)
    3=15-2(6)=[57-2(21)]-2[-1(57)+3(21)] = 3(57)-8(21)

    Appendix: Old Joke. A man calls a friend and says: There's a madman with a gun, hatchet, and a can of gasoline running around your house trying to break in. But that's not why I called.
    Thanks from Melody2
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91

    Re: Modular arithmetic

    Soroban, Thanks for rewriting my first proof in large letters.
    Thanks from romsek
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121

    Re: Modular arithmetic

    Quote Originally Posted by Melody2 View Post
    Hello again,
    My question concerns the Diophantine equation solution.
    I can follow HallsofIvy's solution, at least at a very superficial level, but, firstly, I don't understand why it is more general and, secondly, I can't work out how to apply it to other problems.

    I am considering
    5/286 = x (mod7)
    5=286x (mod7)
    286/7 = 40 and 6/7 therefore 286 mod7 = 6
    6x=5 mod7
    6x = 5, 12,19 etc
    x=2+7N where N is any integer
    ok that's the easy way done with.
    --------------------------------------------------
    now for the other way.
    286x = 7y+5 for some y in the set of integers
    286x-7y=5

    286/7 = 40 +6/7
    286=40(7)+6
    286-40(7)=6 (1)

    7/6 = 1 +1/6
    7 = 6(1) +1
    Sub in (1)
    7 = 286-40(7) +1
    -286+41(7) = 1
    286(-1)-7(-41) =1
    how does this help???
    I'm obviously doing it wrong.

    So my 2 questions are
    What am I doing wrong and why is this way more general?
    Thank you for your patience and your time.
    When I said "more general", I was thinking of situations where you have a much larger "modulus". For example, to solve 3x= 5 (mod 7), the simplest way to do that is to replace x with 0, 1, 2, 3, 4, 5, and 6 and see that 3*4= 12= 5 (mod 7) so that x= 4 is the solution. But if you had 3x= 5 (mod 107) you really don't want to try every number from 0 to 106! Instead note that 3x= 5 (mod 107) means that 3x=107y+ 5 for some integer y. That is the Diophantine equation 3x- 107y= 5. 3 divides into 107 35 times with remainder 2: 107- 35(3)= 2. 2 divides into 3 once with remainder 1: 3- 2= 1. Replacing that 2 with 107- 35(3), 3- (107- 35(3))= 36(3)- 107= 1. Multiplying by 5, 180(3)- 3(107)= 5. So one solution to 3x- 107y= 5 is x= 180, y= 3. Any solution must be of the form x= 180- 107k, y= 3+ 3k.
    Thanks from Melody2
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91

    Re: Modular arithmetic

    Examples of the Euclidean algorithm procedure, including OP for k=p/q:

    If ax=b(modm) and (a,m)=1, then:
    1=sa+tm from Euclidean algorithm,
    b=bsa+btm → b-(bs)a = btm.
    x=bs is the unique solution modm.

    If 7x=8(mod115), (7,115)=1
    1=s(a)+t(m)=s(7)+t(115), from Euclidean algorithm
    115=16(7)+3
    7=2(3)+1, then
    1=7-2(3)=7-2[115-16(7)]
    1=17(7)-2(115)=sa+tm
    s=17, b=8, x=bs=8(17)(mod115)

    Another example of the method is the OP: 1/192=k(mod7). If k=p/q, this becomes:
    192p=q(mod7), (192,7)=1
    1=s(a)+t(m) = s(192)+t(7), from Euclidean algorithm
    192=27(7)+3
    7=2(3)+1, then
    1=7-2(3)=1-2[192-27(7)]
    1=-2(192)+55(7)=sa+tm
    s=-2, b=q,
    p=-2q

    The sols are unique mod7 for q=1,2,3,4,5,6,7. If r=q+n7, r=q(mod7) and 192p=r(mod7) has same solution as 192p=q(mod7) by transitivity.

    If q=4, p=-2(4)(mod7)=-8(mod7)

    Notes:

    If ax=b(modm), both a and b can be rational, again leading to an integer congruence: (35/23)x=27/46(mod15) → 70x=27(mod15). I think the OP was giving a hint of this by using (1/192)=k(mod7).

    If (a,m)=d >1, the solution becomes a little more involved.
    Thanks from Melody2
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Nov 2013
    From
    Australia
    Posts
    176
    Thanks
    36

    Re: Modular arithmetic

    Firstly I want to say thank you to all of you. I really appreciate your efforts to teach me.
    What I really needed to know I got out of the first few posts and I am very pleased about that.

    ---------------------------------------------------------------------
    I've spent considerable time this afternoon trying to work out what HallsofIvy and Hartlw are trying to tell me.
    To the best of my understanding you are both trying to tell me the same thing.
    Maybe I just don't have the pre-knowledge to understand.
    I don’t mind if you give up at this point. I have learned what I set out to learn.
    However, if you want to continue trying to teach me I will continue to do my best to understand.

    ----------------------------------------------------------------------
    I am looking at this example from Hartlw. (I think that your theory might be beyond me)
    Examples of the Euclidean algorithm procedure, including OP for k=p/q:

    If ax=b(modm) and (a,m)=1, then:
    1=sa+tm from Euclidean algorithm,
    b=bsa+btm → b-(bs)a = btm.
    x=bs is the unique solution modm.

    If 7x=8(mod115), (7,115)=1 What does (7,115)=1 mean ?
    1=s(a)+t(m)=s(7)+t(115), from Euclidean algorithm What Euclidean algorithm?
    115=16(7)+3 The next 4 lines of number crunching is easy. That's probably the only bit I understand.
    7=2(3)+1, then
    1=7-2(3)=7-2[115-16(7)]
    1=17(7)-2(115)=sa+tm
    s=17, b=8, x=bs=8(17)(mod115)
    ----------------------------------------------------------------------------------------------------------------

    Now HallsofIvy,
    This was your last post. I split it up so that I could make sense of it.

    "When I said "more general", I was thinking of situations where you have a much larger "modulus". For example, to solve 3x= 5 (mod 7), the simplest way to do that is to replace x with 0, 1, 2, 3, 4, 5, and 6 and see that 3*4= 12= 5 (mod 7) so that x= 4 is the solution.

    But if you had 3x= 5 (mod 107) you really don't want to try every number from 0 to 106! Instead note that 3x= 5 (mod 107) means that 3x=107y+ 5 for some integer y.
    (A) That is the Diophantine equation 3x- 107y= 5. (So far, so good)

    (B) 3 divides into 107 35 times with remainder 2: 107- 35(3)= 2. (alright)

    (C) 2 divides into 3 once with remainder 1: 3- 2= 1. (alright)


    (D) Replacing that 2 with 107- 35(3), 3- (107- 35(3))= 36(3)- 107= 1. (alright)


    (E) Multiplying by 5, 180(3)- 3(107)= 5. [Okay, I can see why you did that, but shouldn’t it be 180(3)– 5(107)=5]

    So one solution to 3x- 107y= 5 is x= 180, y= 3. Any solution must be of the form x= 180- 107k, y= 3+ 3k.

    (F) So one solution to 3x-107y=5 is x=180 and y=5 (alright - if I use my y=5)

    (G) Now I am lost.
    ------------------------------------------------------------------------------

    Thanks guys. Your efforts, past and future if you choose are appreciated.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91

    Re: Modular arithmetic

    There are three things you have to understand:
    1) Definition of congruence
    2) Euclidean Algorithm
    3) Solution of a linear congruence using the Euclidean Algorithm

    2) Euclidean Algorithm:
    Theorem: The greatest common divisor ,gcd, of m and n, (m,n), can be found as the last non-vanishing remainder of the Euclidean Algorithm. There exist integers s and t such that (m,n) = sm+tn

    The Euclidean algorithm is best explained by examples:

    (25,19):
    25= 1(19)+6,……(25,19)=(19,6)
    19=3(6)+1,………(19,6)=(6,1)=1
    6=6(1),…………...
    ie, (m,n) doesn’t change. This part is straightforward but a little hard to grasp.

    (24,18):
    24=1(18)+6…….(24,18)=(18,6)=6
    18=3(6)

    (24,9):
    24=2(9)+6………(24,9)=(9,6)
    9=1(6)+3………..(9,6)=(6,3)=3
    6=2(3)

    (57,21)
    57=2(21) + 15,…….. (57,21)=(21,15)
    21=1(15)+6,……….. (21,15)=(15,6)
    15=2(6)+3,………….(15,6)=(6,3)=3
    6=2(3)

    The proof of the Theorem resides in the fact that the remainders in the Euclidean Algorithm are constantly decreasing so eventually they reach 0, and (m,n) doesn’t change.

    By backward substitution in the above you get (m,n)=sm+tn. In the last example:
    3=15-2(6)
    6=21-1(15)
    15=57-2(21)
    which gives (57,21)=3=3(57)-8(21)=s(57)+t(21)

    1) & 3) ax=b(modm) has a solution if (b-ax)=km
    if (a,m)=1
    1=sa+tm from Euclidean algorithm → b=bsa+btm → b-(bs)a=btm
    x=bs is a solution. x is unique modm requires more explanation. Enough for now.

    If you didn’t understand the other posts, don’t feel bad, neither did I.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Modular arithmetic

    Solving congruences (mod n), if they can be solved, depends on divisibility properties of INTEGERS.

    One basic fact often established, is that the gcd of two integers, a and b, satisfies what is called a Bezout identity:

    If gcd(a,b) = d, then there exist integers r,s with ra + sb = d.

    One way to PROVE this, is to actually find the integers r and s. Since it makes no difference what sign a and b have (because their gcd is always positive), we may as well assume b > a > 0 (if one of a or b is 0, then gcd(a,b) = max(|a|,|b|), and if both are 0, there IS no greatest common divisor since ALL integers divide 0).

    Hartlw's previous post shows you how to use "long division" to actually find the gcd, and "working backwards", how to find r and s.

    If it so happens that gcd(a,b) = 1, this means we have integers r,s such that ra + sb = 1.

    Now, if we have an equation:

    ak = 1 (mod n), or equvialently: 1/a = k (mod n), we can only solve it if gcd(a,n) = 1.

    Why? well suppose gcd(a,n) = d > 1. This means there is some 1 < t < n, and some 1 < u < n with:

    dt = a
    du = n.

    so au = (dt)u = (td)u = t(du) = tn, which means:

    au = 0 (mod n).

    So if we had some k with:

    ak = 1 (mod n), then:

    u = u(ak) = (ua)k = (au)k = 0k = 0 (mod n). In other words n divides u, which is impossible since 1 < u < n.

    On the other hand, if gcd(a,n) = 1, we can find integers r,s with ra + sn = 1.

    Thus:

    ra + sn = 1 (mod n)

    ra = 1 - sn = 1 (mod n),

    and then r (mod n) is the number we are looking for.

    Note that this doesn't always work:

    1/3 = x (mod 6), equivalent to 3x = 1 (mod 6).

    in this case, gcd(3,6) = 3 > 1, so we would expect NO solutions, and indeed:

    3*0 = 0 (mod 6)
    3*1 = 3 (mod 6)
    3*2 = 6 = 0 (mod 6)
    3*3 = 9 = 3 (mod 6)
    3*4 = 12 = 0 (mod 6)
    3*5 = 15 = 3 (mod 6)

    If the modulus is PRIME (like 7 in your example) this always works. Every residue mod p has a multiplicative inverse. This is not "obvious".

    As an explanation, Hartlw uses the notation (a,b) to mean gcd(a,b), which is common in some texts. I could explain WHY this notation is sometimes used, but I am afraid the explanation would be a bit over your head. Suffice to say that (a,b) is the smallest subset of the integers containing all integers k for which a|k and b|k and is closed under addition and multiplication.

    let's use HallsofIvy's example of modulus 107, to find the inverse of 18 (mod 107).

    So first we need to find r,s so that:

    18r + 107s = 1.

    1) 107 = 18*5 + 17
    2) 18 = 17*1 + 1
    3) 17 = 17*1 + 0 <---remainder vanishes, use previous step

    1 = 18 - 17*1 = 18 - 17 <---18 is in our formula, but 107 isn't, yet.
    17 = 107 - 18*5 (from step 1)
    1 = 18 - 17 = 18 - (107 - 18*5) (substituting 107 - 18*5 in for 17)
    1 = 18 - 107 + 18*5 = 18(1 + 5) - 107 = 18*6 - 107

    so r = 6, and s = -1.

    So, it should be the case that 18*6 = 1 (mod 107). Let's check:

    18*6 = 108 = 1 + 107*1, so, yep.

    Now we can solve 18x = y (mod 107) for ANY y:

    18x = y (mod 107)
    6(18x) = 6y (mod 107)
    (6*18)x = 6y (mod 107)
    x = 6y (mod 107)

    In other words, "dividing by 18" in mod 107 is the same as multiplying by 6. This may take some getting used to, since the "18" and "6" in mod 107 do not behave like "ordinary" integers 18 and 6.
    Thanks from Melody2
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. help with modular arithmetic please
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 2nd 2011, 02:50 AM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 6th 2011, 02:14 AM
  3. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 01:37 PM
  4. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 28th 2008, 12:29 AM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum