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 = 345
a = 17
b//a = 20
b%a = 5
gcd(345, 17) = gcd(17, 5) = gcd(5, 2) = gcd(2, 1) = gcd(1,0) = 1
b = 17
a = 5
b//a = 3
b%a = 2
b%a
b a r
345 = 17(20) + 5
17 = 5(3) + 2 b, a = a, b%a "shift"
5 = 2(2) + 1
2 = 1(2) + 0
while b%a > 0:
b, a,= a, b%a
Warning: Explicit This video shows how to get an explicit formula for the Fibonacci numbers.
Prime Numbers
552
/ \
4 138
/ \ / \
2 2 6 23
/ \
2 3