1. q|(a+b) because a & b are both divisible by q

2. if there exists 'c' that is Z, then q|ca

3. if c & d are Z, then q|(a+db)

4. if q|a and  a|b, then by the transitive property q|b

5. a=bq+r

1. use the division algorithm, if r=0 then b|a (a,b)=d

2. if r does not equal 0 then there exists q1, r1 so that b=q1r+r1 where o<=r2<r1

Every composite integer N can be written as a product of a prime. N=p1*p2...*pk

- N/p2p1 are lN

ax+by=c where (a,b) does not divide 'c'

- ax+by=(a,b)

- since (a,b)| a & b, the (a,b)|(ax+by)=c, thus (a,b)|c 

- there are no solutions for x and y if (a,b) does not divide 'c'

-X=Xo + bt & Y=Yo - at

= is congruence

1. Add: a mod n & b mod n is the same as (a+b) mod n.

2. Reflexive property: a= a mod m

3. Symmetric property: a= b mod m iff b=a mod m

4. Transitive Property: if a=b mod m and b=c mod m then a=c mod m

= is congruence

1. if a=b mod m and c=d mod m then a+c=b+d mod m

2. if a = b mod m and c=d mod m then ac=bd mod m

-implies that if a=b mod m then  3a = 3b mod m

3. If ac = bc mod m and if (c,m)'='1, then a=b mod m 

Theorem: ax=b mod m

= is congruence

1. if (a,m) does not divide b then there are no solutions

2. (a,m)=d|b, then there are d solutions

3. if (a,m)=1 there is 1 solution

4. 

= is congruence

1. x=1 mod3, x=2 mod4, x=6 mod7;(3,4,7 are pair wise)

2. x'='1+3K1=2 mod 4

3. 3K1= 1 mod 4; K1=3 mod 4

4. K1'='3+4K2; X'='1+3(3+4K2)'='10+12K2

5. 10+12K2=6 mod 7; 12 mod 7'='5

6.5K2= 3mod 7; 10 mod 7'='3

7.K2=2 mod 7; K2=2+7K3

8.x=34+84K3; 84 is the product of the moduli so x=34 mod 84; 1st range:0<=x<83 x=34

83<=x<167(84+83) x=118

-let p be prime, then if (a,p)'='1, a^(p-1)=1 mod p

-P=5:

            a     a^(2)     a^(3)       a^(4)   mod 5

                   1       1            1             1

                   2       4            3             1

                   3       4            2             1

                   4       1            4             1

The set of numbers between 1 and m-1 that are relatively prime to m.

- phi(m) is the number of elements in the RRS mod m; number of elements less than m that are relatively prime to it

-E.G: m=6 RRS: {1,5} phi(6)=2

- if (a,m)'='1, then the smallest integer t so that a^(t)=1 mod m is the order of a mod m, (order a)

-a^(phi(m))=1 mod m.