Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 7 of 7
  1. MHB Journeyman
    Petrus's Avatar
    Status
    Offline
    Join Date
    Feb 2013
    Posts
    739
    Thanks
    1,187 time
    Thanked
    773 times
    Thank/Post
    1.046
    Awards
    MHB Model User Award (Jan-June 2013)
    #1
    Hello MHB,
    I have hard understanding what we doing when we solve
    $ \displaystyle 35y \equiv 13(mod\ 97)$
    I understand we can rewrite that as
    $ \displaystyle 35y = 13+97m$
    if we replace $ \displaystyle m=-x$ we got
    $ \displaystyle 97x+35y=13$
    I get $ \displaystyle gcd(97,35)=1 $ that means we will have one soloution.
    and the diophantine equation got soloution for $ \displaystyle y=-468+97k
    $ and what shall I do next?

    Regards,

  2. MHB Journeyman
    Petrus's Avatar
    Status
    Offline
    Join Date
    Feb 2013
    Posts
    739
    Thanks
    1,187 time
    Thanked
    773 times
    Thank/Post
    1.046
    Awards
    MHB Model User Award (Jan-June 2013)
    #2 Thread Author
    Hello MHB,
    I finally saw what I did wrong! for people who is intrested the soloution will be $ \displaystyle k=5 <=> y=17$
    What have we exactly calculated?
    this is what we calculated:
    $ \displaystyle 35y \equiv 13(mod\ 97)$
    if we $ \displaystyle 35*17=595$ with other words if we take away 13 from 595 and divide by 97 we will get a integer as result so
    $ \displaystyle 595-13= 582$ and now to se we get no rest with divide by 97.
    $ \displaystyle \frac{582}{97}=6$ so we solved it correctly!
    Regards,
    Last edited by Petrus; April 21st, 2013 at 13:02.

  3. MHB Master
    MHB Site Helper
    MHB Math Helper
    chisigma's Avatar
    Status
    Offline
    Join Date
    Feb 2012
    Location
    Beograd, Serbia
    Posts
    1,704
    Thanks
    393 times
    Thanked
    3,370 times
    Thank/Post
    1.978
    Awards
    MHB Statistics Award (2014)  

MHB Statistics Award (Jan-June 2013)
    #3
    Quote Originally Posted by Petrus View Post
    Hello MHB,
    I finally saw what I did wrong! for people who is intrested the soloution will be $ \displaystyle k=5 <=> y=17$
    What have we exactly calculated?
    this is what we calculated:
    $ \displaystyle 35y \equiv 13(mod\ 97)$
    if we $ \displaystyle 35*17=595$ with other words if we take away 13 from 595 and divide by 97 we will get a integer as result so
    $ \displaystyle 595-13= 582$ and now to se we get no rest with divide by 97.
    $ \displaystyle \frac{582}{97}=6$ so we solved it correctly!
    Regards,
    Given the first order diophantine equation...

    $\displaystyle 35 \cdot y \equiv 13\ \text{mod}\ 97$ (1)

    ... a standard way to solve it is to multiply both members by the multiplicative inverse of 35, if that multiplicative inverse do exists, obtaining...

    $\displaystyle y \equiv 35^{-1} \cdot 13\ \text{mod}\ 97$ (2)

    If n is prime, then any number mod n different from zero has one and only one multiplicative inverse. In Your case 97 is prime and the multiplicative inverse of 35 is 61 because $\displaystyle 35 \cdot 61 = 2135 = 97 \cdot 22 + 1$, so that the solution is...

    $\displaystyle y = 61 \cdot 13 = 793 \equiv 17\ \text{mod}\ 97$ (3)

    Kind regards

    $\chi$ $\sigma$

  4. MHB Craftsman

    Status
    Offline
    Join Date
    Feb 2012
    Location
    Lexington, MA, USA
    Posts
    409
    Thanks
    167 times
    Thanked
    1,389 time
    Thank/Post
    3.396
    Awards
    MHB Chat Room Award (2014)  

MHB Chat Room Award (Jul-Dec 2013)  

MHB Humor Award (Jan-June 2013)
    #4
    Hello, Petrus!

    Quote Quote:
    Solve: .$ \displaystyle 35y \,\equiv\, 13\text{ (mod 97)}$

    We have: .. .$ \displaystyle 35y \:\equiv\:13\text{ (mod 97)}$

    . . . . . . . . . $ \displaystyle 35y \:\equiv\:-84\text{ (mod 97)}$

    Divide by 7: .$ \displaystyle 5y \:\equiv\:-12\text{ (mod 97)}$

    Then: .$ \displaystyle 5y \:=\:-12 + 97k$

    Hence: .$ \displaystyle y \:=\:\frac{97k-12}{5} \:=\:19k-1 + \frac{2k-7}{5}$

    Since $ \displaystyle y$ is an integer, $ \displaystyle 2k-7$ must be a multiple of 5.
    This happens when $ \displaystyle k = 1.$


    Therefore: .$ \displaystyle y \:=\:19(1) - 1 + \frac{2(1)-7}{5} $

    . . . . . . . . .
    $ \displaystyle y \:=\:17\text{ (mod 97)}$

  5. MHB Journeyman
    Petrus's Avatar
    Status
    Offline
    Join Date
    Feb 2013
    Posts
    739
    Thanks
    1,187 time
    Thanked
    773 times
    Thank/Post
    1.046
    Awards
    MHB Model User Award (Jan-June 2013)
    #5 Thread Author
    Quote Originally Posted by chisigma View Post
    Given the first order diophantine equation...

    $\displaystyle 35 \cdot y \equiv 13\ \text{mod}\ 97$ (1)

    ... a standard way to solve it is to multiply both members by the multiplicative inverse of 35, if that multiplicative inverse do exists, obtaining...

    $\displaystyle y \equiv 35^{-1} \cdot 13\ \text{mod}\ 97$ (2)

    If n is prime, then any number mod n different from zero has one and only one multiplicative inverse. In Your case 97 is prime and the multiplicative inverse of 35 is 61 because $\displaystyle 35 \cdot 61 = 2135 = 97 \cdot 22 + 1$, so that the solution is...

    $\displaystyle y = 61 \cdot 13 = 793 \equiv 17\ \text{mod}\ 97$ (3)

    Kind regards

    $\chi$ $\sigma$
    Hello,
    I wounder if it's anything wrong with the way I solve it? I just feel safe with it and I think that is the way we are supposed to solve it, well that is what I did and get correct answer.

    Regards,

  6. MHB Master
    MHB Site Helper
    MHB Math Helper
    chisigma's Avatar
    Status
    Offline
    Join Date
    Feb 2012
    Location
    Beograd, Serbia
    Posts
    1,704
    Thanks
    393 times
    Thanked
    3,370 times
    Thank/Post
    1.978
    Awards
    MHB Statistics Award (2014)  

MHB Statistics Award (Jan-June 2013)
    #6
    Quote Originally Posted by Petrus View Post
    Hello,
    I wounder if it's anything wrong with the way I solve it? I just feel safe with it and I think that is the way we are supposed to solve it, well that is what I did and get correct answer.

    Regards,
    The great scope of Math is not to solve day by day the occasional problems one meets but to supply instruments to solve specific problems no matter how complex they are. In the modern cryptography diophantine equations similar to one You have proposed but with n a very large prime number are usual and some powerful algorithms for 'fast' discovery of the inverse multiplicative inverse of a number mod n with n very large prime have been found...


    Kind regards


    $\chi$ $\sigma$
    Last edited by chisigma; April 22nd, 2013 at 14:26.

  7. MHB Master
    MHB Global Moderator
    MHB Math Helper
    MHB Ambassador
    Sudharaka's Avatar
    Status
    Offline
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,612
    Thanks
    7,503 times
    Thanked
    2,531 times
    Thank/Post
    1.570
    Awards
    University POTW Award (Jan-June 2013)
    #7
    Quote Originally Posted by Petrus View Post
    Hello,
    I wounder if it's anything wrong with the way I solve it? I just feel safe with it and I think that is the way we are supposed to solve it, well that is what I did and get correct answer.

    Regards,
    Hi Petrus,

    To know whether you solved using a correct method that applies to any Diophantine equation we need some more details. In your post #1, you haven't actually written down how you obtained, \(y=-468+97k\).

Similar Threads

  1. Diophantine equation
    By Petrus in forum Number Theory
    Replies: 24
    Last Post: April 20th, 2013, 18:52
  2. Find 'n' in modulo equation
    By Albert in forum Challenge Questions and Puzzles
    Replies: 7
    Last Post: January 29th, 2013, 23:35
  3. Diophantine equation second grade
    By Lolyta in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 1
    Last Post: March 28th, 2012, 05:41

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards