MATHmaniac aka CrUNchy

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:

a)

b)If then,

c)If ,and then

d)If and then, and

e)If ,then and

f)If then for any k>0

THEOREM 16
Let be a polynomial function of X with integral coefficient . If then

THEOREM 17
Let be the decimal expansion of the positive integer N, where
. Let . Then a/N iff a/S.

THEOREM 18
Let be the decimal expansion of the positive integer N, where . Let . Then 11/N iff 11/T.

THEOREM 19
Let be the decimal expansion of the positive integer N, where .Then 2/N iff its unit digit is 0,2,4,6, or 8.

THEOREM 20
Let be the decimal expansion of the positive integer N, where . Then 4/N iff 4/P

THEOREM 21
The Linear Congruence has a solution iff d/b, where d= gcd(a,n). If d/b then it has d in congruent solution modulo n. If is any solution of then the d in congruent solution are given by , where t=0,1,...,d-1

CHINESE REMAINDER THEOREM
Let be positive integers such that for . Then the system of Linear Congruences:




has a simultaneous, which is unique modulo the integer .


FERMAT'S THEOREM
Let p be a prime and suppose that