Results 1 to 2 of 2

Math Help - Linear Congruences

  1. #1
    Newbie
    Joined
    Dec 2008
    From
    Philadelphia
    Posts
    24

    Linear Congruences

    How do i prove that for every prime p > 5, the following system has a solution:

    7x + 3y = 1 mod p
    4x + 6y = -1 mod p
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    Solve like a pair of linear equations

    Why not try solving this like a pair of linear equations?

    Multiply the 1st equation by 2 and subtract the 2nd to get:
    10x = 3 mod p. This has a solution since (10,p)=1 so there exists a y such that 10 * y = 1(p). Then x = 3 * y (p).
    Once you have x,
    <br />
y = ( 1 - 7 * x) * 3  ^ {-1} mod (p)<br />
    and again because (3,p)=1 you know that the inverse of 3 exists.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Linear Congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 26th 2011, 09:28 PM
  2. solving linear congruences...please help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 30th 2010, 02:07 AM
  3. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 19th 2009, 09:33 PM
  4. linear congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 23rd 2008, 08:27 PM
  5. linear congruences
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: August 14th 2008, 09:40 AM

Search Tags


/mathhelpforum @mathhelpforum