Number Theory, Continued
Last time we learned about the relation | on integers.
We defined d|a if
d
divides into
a
evenly. In Python we test for this using the predicate
a%d == 0. We also know that for any integer
d, d | 0 and that for any integer
a,
1|a and
-1|a.
Hence we can ignore sign when looking at divisibility. However we will place our focus on nonnegative integers.
If a and
b
are integers that are not both 0, we define
gcd(a,b) to be the greatest common divisor
of
If a and
b.
Such a thing exists for two reason. Firstly, 1 is a divisor
of all integers, so any pair of integers has 1 as a common
divisor. Secondly, for any integers
a
b,
all common divisors must occur between 1 and min(a,b).
So, we can loop through these numbers and find the
common divisor that is the largest.
This python function will check to see if
d is a common divisor
a
and
b
def is_common_divisor(d, a, b):
return a%d == 0 and b%d == 0
So here is one way to compute a gcd.
def gcd(a,b):
if a == 0 and b == 0:
raise ValueError
a = abs(a)
b = abs(b) ##throw out signs
n = min(a,b)
out = 1
for k in range(2, n+1):
if is_common_divisor(k, a b):
out = k
return out
This algorithm is O(n) because it is at worst proportional
to the size of the problem. You have to perform all of the
checks from 2 to n - 1. However, there is a smarter
way to do this.
Euclid's Algorithm
Last Time We learned that if
b = a*q + r that
gcd(b,a) = gcd(a,r).
We also know this is true for all integers
b and a with the proviso that
a != 0.
b = a*(b//a) + b%a
b = 374 a = 21 b //a = 17 b % a = 17 21*17 + 17 357 + 17 374
gcd(1088, 150) = gcd(150, 38)
= gcd(38, 36)
= gcd(36, 2)
= gcd(2, 0) = 2
b a r = (b%a)
150 = 1088(0) + 150
1088 = 150(7) + 38
150 = 38(3) + 36
38 = 36(1) + 2
36 = 2(18) + 0
13 = 8*1 + 5
8 = 5*1 + 3
5 = 3*1 + 2
3 = 2*1 + 1
2 = 1*2 + 0
F_n roughly equal to 1/sqrt(5)*( (1 + sqrt(5))/2)**n
fibonacci numbers are the slowest
they grow exponentially.
So euclid resolves in O(log(n)) time
Prime Numbers
An integer is prime if its only divisors are 1 and itself.
244
/ \
2 122
/ \
2 61
244 = 2*2*61
Start at 2. see if n%2 == 0; if not
`