1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solutions to Congruence Modulo 50

  1. Jan 12, 2013 #1
    1. The problem statement, all variables and given/known data
    Find all solutions to the equation ##35x\equiv 10mod50##

    3. The attempt at a solution

    gcd( 35,50)= 5
    So, there is a solution to this, since 5| 10. Also, there is a theorem that guarantees the existence of exactly 5 solutions.

    Now, dividing ##35x\equiv 10mod50## over 5 gives:
    ##7x\equiv 2mod10##
    Now, what multiple of 7 gives us ##\equiv 2mod10##
    { 2, 12, 22, 32, 42,...} Here, we found 42 that is a multiple of 7 and satisfies ##\equiv 2mod10##
    We can write ##7x\equiv 42mod10## . Now, I divided the expression by 7 and got ##x\equiv 6mod10##

    Now, there is another theorem that tells me this
    6+(50/5)t, t=0, 1, ..., 4
    I get: 6, 16, 26, 36, 46
    So, the solutions are
    ##x\equiv 6mod50## , ##x\equiv 16 mod50##, ##x\equiv 26 mod50##, ##x\equiv 36mod 50##, ##x\equiv 46mod 50##
    These are the 5 solutions of ##35x\equiv 10mod50##

    I found other solutions online:
    So x = 6, 16, 22, 28, 34, 40, 46 modulo 50 are the
    solutions to the congruence 35x ≡ 10 mod 50.

    Am I incorrect?


    Thank you.
     
  2. jcsd
  3. Jan 12, 2013 #2
    Your method is correct. You can check your own solutions to verify that they are correct.

    35*6 = 210 which is congruent to 10 mod 50.
    35*16 = 560 which is also congruent to 10 mod 50.
    Similarly for the other solutions that you found.

    You can verify that 22, 28, and 40 are not solutions.
    35*22 = 770 which is 20 mod 50.
    35*28 = 980, is 30 mod 50.
    etc.
     
  4. Jan 12, 2013 #3
    I have read somewhere that division is not defined in modular arithmetic. Can someone tell me how this affect my solution?

    @kru: This is puzzling, since I found those other solutions at a .edu site.
     
  5. Jan 12, 2013 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Division is not necessarily defined in modular arithmetic because there may be "0 divisors". For example, in modulo 6, 2(3)= 6= 0 (mod 6). If we had an equation of the form 3x= 1 (mod 6) we can immediately check that 3(1)= 3, 3(2)= 6, 3(3)= 9= 3, 3(4)= 12= 0, and 3(5)= 15= 3 mod 6. There is NO x such that 3x= 1 and so we could not, for example, "divide by 3" to get "1/3" as an answer. If we are working "modulo" a prime number, that doesn't happen and we can define "division".

    The way I would do "35x= 10 mod 50" is this. This is the same as saying 35x= 50n+ 10 for some integer n- a linear "diophantine equation". The first thing we can do divide through by 5 to 7x= 10n+ 2 or 7x- 10n= 2. Now 7 divides into 10 once with remainder 3: 3= 10- 7. 3 divides into 7 twice with remainder 1: 1= 7- 2(3). We can replace that "3" with 10- 7 from the first equation: 1= 7- 2(10- 7)= 3(7)- 2(10)= 1 (The "Euclidean Divison Algorithm"). Multiply through by 2 to get 6(7)- 4(10)= 2.

    So one solution to 7x- 10n= 2 is x= 6, n= 4. It is possible to write out the "general solution" but since 6 itself is between 0 and 10, x= 6 satisfies 7(6)= 2 (mod 10) and so 35(6)= 210= 10 (mod 50).
     
  6. Jan 12, 2013 #5
    According to Wikipedia, Diophantine equations are written as follows:
    ax + by = c
    The Diphantine equation that you are really writing is this
    35x-50n=10?


    I understand everything, until you change the equation 1=7 -2(10-7)= 3(7)-2(10)=1. I understand that 21-20=1, but why changing from 7- 2(10-7) to 3(7)-2(10)?
    Also, I am acquainted with Euclid's GCD algorithm:
    Euclid(a,b)
    if b==0
    return a
    else return Euclid (b, a mod b)

    Is there a way to use it without having to trace it?


    Is this all solutions for 35x [itex]\equiv[/itex] 10 mod 50? Also, is it correct that there has to be exactly 5 solutions, since the gcd of 35, 50 is 5?
    Is my solution correct?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook