# Linear Congruences

• November 19th 2009, 07:04 AM
Zero266
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
• November 19th 2009, 08:02 PM
qmech
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,
$
y = ( 1 - 7 * x) * 3 ^ {-1} mod (p)
$

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