p is not factor a
Let say a=8,p=4
Solution:
Since p is an odd prime,consider p-1 integers 1,2,3,...p-1,then none of the integers is divisible by p.From Fermat's little theorem .So,
It follows that
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
THEOREM 1 (DEVISION ALGORITHM)
Given integers a and b,with b>0 there exist unit integers q and r satisfying:
a=qb+r
The integers q and r are called respectively the quotient and remainder in the divison of a and b.
DEFINISION:
An integers b is said to be divisible by n integers ,in symbols a/b if there exist some integers c such that b=ac.we say b is not divisible by a.
a/b -> c such that b=ac.
THEOREM 2:
for integers a,b,c the folowing holds:
a)a/0,1/a,a/a
b)a/1 if
c)If a/b and b/c then a/c
Proof:
since a/b and c/d there exist e and f such that b=ea and d=cf.Because bd=ae.cf=ac.ef thus ac/bd.
d)If a/b and b/c then a/c
Proof:
since a/d and a/c there exist e and f such that b=ae and c=bf.Because c=bf=a.ef thus a/c.
e)a/b and b/a iff .
f)if a/b and a/c,then a/c(bx+cy) for some integers x and y.
Proof:
Since a/b and a/c there exist integers e and f such that b=ae and c=af.
Hence, bx+cy=aex+afy=a(ex=fy).Let w=ex+fy,bx+cy=aw, thus a/(bx+cy) for some integers x and y.
THEOREM 3
Given integers a and b.not both 0,which are r,there exist integers x and y such that gcd(a,b)=ax+by.
THEOREM 4
If gcd(a,b)=d,then gcd(a/d,b/d)=1
Proof:
Since gcd(a,b)=d then exist x and y such that d=ax+by. Divide both side by d to obtain 1=(a/d)x+(b/d)y. Because d is commond divisor of a and b,then it is sure that a/d and b/d are integers. Thus,gcd(a/d,b,d)=1.
THEOREM 5
Let a and b be integers not both 0.then a and b are relatively prime if and only if there exist integers x and y such that 1=ax+by.
THEOREM 6
If gcd(a,b)=d then gcd(a/d,b/d)=1
THEOREM 7
If a/c and d/c with gcd(a,b)=1 then ab/c.
THEOREM 8
If a/bc with gcd(a,b)=1 then a/c.
THEOREM 9
Let a,b be integers,not both 0 or a positive integers d, d=gcd(a,b) iff :
a)d/a and d/b
b)Whenever c/a and c/d then c/d
THEOREM 10
If a=bq+r then gcd(a,b)=gcd(b,r).
THEOREM 11
If k>0 then gcd(ka,kb)=k gcd(c,b).
THEOREM 12
The Linear Diphantine Equation ax+by+c has a solution iff d/c, where d=gcd(a,b). If is any particular solution of this equation,the all other solution are given by
where t is any integers.
THEOREM 13
If gcd(,b)=1 and ,
, is a particular solution of the Linear Diophantine Equation ax+by=c, then all solution are given by:
and
for any integers t.
THEOREM 14
for any integers a and b, iff a and b leave the same nonnegative remainder when divide by x.
THEOREM 15
let n>1 be fixed and a,b,c,d be any integers.The following properties holds:
