MATHmaniac aka CrUNchy

The linear congruences has a solution iff d/b.Where d=gcd(a,n).If d/b,then it has d mutually incongruent solution modulo n

Example:

34-60=98y
34x-98y=60
using E.A we evaluate gcd(34,98).The compation are as follow:

98=2*34+30
34=1*30+4
30=7*4+2
4=2*2+0

Since the gcd(34,98)=2, and 2/60,the equation 34-98y=60.

To obtain the integers 60 is a linear combination of 98 and 34,we work backward through the previous coputation as follow:

2=30-7*4
4=34-1*30
98=30-2*34

Upon multiplying the relation by 30,we obtain:

2=30-7*4
2=30-7(34-1*30)
2=30-7*34+7*30
2=8*30-7*34
2=8(98-2*34)-7*34
2=8*98-16*34-7*34
2=8*98-23*34

multiply both side by 30

60=(240)98-(690)34



x=-690+(98/2)t

when t=0
x=-690
when t=1
x=-641

-69o=-7*98+(-4)


-641=-588-53


Then,x=94 and 45

• 
• 
• 
• 
•