What is number theory?

    It is all about integers.
    

    Suppose x and z ar real numbers.
    Is there a number y so x*y = z?

    y = z/x.

    x != 0


    2, 5
    
    2*x = 5  has NO SOLUTION in the integers.
    Divisibility of integers is a non-trivial question.

    5%2 -> 1

    We say d|a if there is some integer q so that a = d*q

    d is a divisor of a
    d is a factor of a
    a is a multiple of d.

    Question

    What number(s) divide every integer?

    1, -1 

    34534 = (-1)(34534) = (1)(34534)

    1, -1 are universal divisors.
    
    what number is divisible by EVERY integer?

    0   

    n(0) = 0, so n|0

    ----------------------------------------

    How do we know if a number is divisible by 5?
    number ends in 5 or 0

    How do we know if a number is divisble by 3?
    if sum of digits is divisable by 3.

    How do we know if a number is divisible by 9?
    if sum of digits is divisible by 9.

    How do we know if a number is divisible by 2?
    if last digit is even

    How do we know if a number is divisble by 4?
    if the last two digits are divisible by 4.

    2345234324123431243492 = 2345234324123431243400 + 92

    ------------------------------------------------

    Naughty: we will not use 0 as a divisor.

    suppose d|a and d|b.

    d|a says there is some integer q so a = dq
    d|b says there is some integer s so b = ds

    a + b = dq + ds = d(q + s).  Note: q + s is an integer!
    a - b = dq - ds = d(q - s).  Note: q - s is an integer!
    d | a + b
    d | a - b

    Suppose c is an integer, and d|a.

    ac = cdq = d(cq)  d | ac  (a multiple of a multiple is a multiple)

    if d|a and d|b and x and y are ANY integers,

    d| ax + by   

    Arithmetic:  + - * // ** (to nonnegative integer powers)

    %

    b = a*(b//a) + b%a

    if b%a == 0, then a|b
    b = 37
    a = 5
    b//a = 7
    b%a = 2

    37 = 5*7 + 2
 
Greatest Commond Divisors.

If a and b are integers and d|a and d|b, we say d is a common divisor of a and b.

gcd(8, 0) = 

1|8 and 1|0           1
2|8  and 2| 0         2
3|8  is false         2
4|8  and 4| 0         4
5|8 false
6|8 false
7|8 false
8|8 and 8| 0          8

gcd(8, 0) = 8.
gcd(17, 0) = 17
gcd(-17, 0) = 17
gcd(a, 0) = abs(a)   a != 0
gcd(a, b) = gcd(b, a)  


If a and b are any integers, 1 is a common divisor.
any common divisor d must statisfy 1 <= d <= min(a,b)

n = min(abs(a), abs(b))
start at 1 and set out = 1
go to 2, if 2|a and 2|b, out = 2
go to 3, if 3| and 3|b out = 3 

.
.
.
go to n, i n|a and n|b out = n
return out