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

Printable View

- Nov 19th 2009, 07:04 AMZero266Linear 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 - Nov 19th 2009, 08:02 PMqmechSolve 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,

$\displaystyle

y = ( 1 - 7 * x) * 3 ^ {-1} mod (p)

$

and again because (3,p)=1 you know that the inverse of 3 exists.