# 2015.11.23 Project

## 2371 days ago by krsteph

Kylie Stephens

MATH 3600

C10726950

This project will focus on two function my_gcd and my_poly_gcd which will compute the greatest common denominator for two integers and then two polynomials, respectively. First, let's look at some notes about finding the greatest common denominator.

Greatest Common Divisor

Fact: any integer can be written as a product of primes: $p_1, p_2, ... , p_k$ in a unique way if we insist $p_1 \leq p_2 \leq ... \leq p_k$

If we have two integers $m$, $n \geq 1$, say.

If we have a number $d$ so that $\frac{d}{n}$ ($d$ divides $n$, that is, $n = d.k$ for some integer $k$), and $\frac{d}{m}$, then $d | (n - m)$ as well ($m = d.L$ $\rightarrow$ $n - m = d(k -1)$).

A little thought then shows ($d|n$ and $d|m$) $\leftrightarrow$ ($d|m$ and $d|(n - m))$.

So, given a pair of integers $n$, $m$:

Ex: 39 and 12

($d|39$ and $d|12$) $\leftrightarrow$ ($d|12$ and $d|27$)

$\leftrightarrow$  ($d|27$ and $d|12$) $\leftrightarrow$  ($d|12$ and $d|15$)

$\leftrightarrow$  ($d|15$ and $d|12$) $\leftrightarrow$  ($d|12$ and $d|3$)

$\leftrightarrow$  ($d|3$ and $d|9$) $\leftrightarrow$  ($d|9$ and $d|3$)

$\leftrightarrow$  ($d|3$ and $d|6$) $\leftrightarrow$  ($d|6$ and $d|3$)

$\leftrightarrow$  ($d|3$ and $d|3$) $\leftrightarrow$  $d|3$

At the end of this process, we find one number which will be the biggest number which divides both $n$ and $m$.

Def: The greatest common divisor, (gcd($m$,$n$)) of $m$ and $n$ is the largest integer which divides both $n$ and $m$.

Fact: This algorithm will find it.

The Division Theorem:

Given an integer $a$ and a positive integer $b$, we can find unique integers $q$, $r$ with $0 \leq r < b$ so that $a = qb + r$.

Ex: $a = 39$   $b = 12$   : $3 * 12 + 3$    $q = 3$    $r = 3$

$a = -39$  $b = 12$   : $(-4) * 12 + 9$q = -4    $r = 9$

Corollary:

If $a,b \in Z$ with $b > 0$ and $a = qb + r$ from Divison Theorem, then ($d|a$ and $d|q$) $\leftrightarrow$ ($d|b$ and $d|r$).

Corollary:

$gcd(a,b) = gcd(b,r)$

Ex: $q = 652$   $b = 60$

$652 = 10 * 60 + 52$    $q = 10$   $r = 52$       $gcd(652,60)$

($60 = 1 * 52 + 8$      $q = 1$      $r = 8$)      = $gcd(60,52)$

($52 = 6 * 8 + 4$        $q = 6$     $r = 4$)       = $gcd(52,8)$

($8 = 2 * 4 + 0$         $q = 2$     $r = 0$)       = $gcd(8,4)$

$d|652$ and $d|60$ $\leftrightarrow$ $d|4$ or $gcd(652,60) = 4$

If $gcd(a,b) = d$, then we can find integers $x,y$ so that $ax + by = d$.

$p$ is prime if it is divisible only by 1, $p$.

$p|ab \leftrightarrow$ either $p|a$ or $p|b$

Suppose $p|ab$, but $p \nmid a$.

$p \nmid a \rightarrow gcd(a,p) = 1$  (since only positive divisiors of $p$ are 1 and $p$)

So, we can find $x$,$y$ so that $ax + py = 1$.

Then, $abx + pby = b$

$p|ab$    $p|p \rightarrow p|b$

Let's begin this project by writing our own function my_gcd($a,b$) that will return the greatest common denominator, $d$, where $d = gcd(a,b)$.

def my_gcd_ab(a,b): if a == b: return a else: if a > b: dividend = a #switch a and b divisor = b else: divisor = a #assign one to be the divisor and one to be the dividend dividend = b q = floor(dividend/divisor) #this takes the floor of a/b r = dividend - q*divisor while r > 0: dividend = divisor divisor = r q = floor(dividend/divisor) r = dividend - q*divisor d = divisor return d

To make sure this function works and returns the greatest common denominator, let's test a few integers.

my_gcd_ab(20,100)
 20 20
my_gcd_ab(30,100)
 10 10
my_gcd_ab(38,8)
 2 2

Now that we have tested our my_gcd function, let's write one that computes the x and y so that $ax + by = d$. Note that if $a$ and $b$ are equal, the values for x and y will come from our first function.

def my_gcd(a,b): if a>b: if b==0: return (1,0) else: q = a//b #takes the floor of a/b r = a - q*b m, n = my_gcd(b, r) #takes the function with respect to the divisor and remainder return (n,m-q*n) #x=t and y=s-q*t elif a<b: if a==0: return (0,1) else: q = b//a r = b - q*a m, n = my_gcd(a, r) #takes the function with respect to the divisor and remainder return (m-q*n,n) #y=t and x=s-q*t else: return my_gcd_ab(a,b)
a=724 b=107 x,y = my_gcd(a,b) print [my_gcd_ab(a,b),x,y] #print d = a*x + b*y
 [1, -30, 203] [1, -30, 203]
a = 150 b = 248 x,y = my_gcd(a,b) print [my_gcd_ab(a,b),x,y]
 [2, 43, -26] [2, 43, -26]
a = 240 b = 242 x,y = my_gcd(a,b) print [my_gcd_ab(a,b),x,y]
 [2, -1, 1] [2, -1, 1]

How to divide polynomials:

Use synthetic or long division.

We want a remainder $\frac{r(x)}{b(x)}$ with $deg(r(x)) < deg(b(x)$.

Need: How to find quotients and remainders for poly nomial division.

$a(x) = 3x^4 + 3x^3 + 7x^2$

$b(x) = x^2 + 2x + 6$

We want to write $\frac{a(x)}{b(x)} = q(x) + \frac{r(x)}{b(x)}$ with $deg(r(x)) \leq 1$.

$q(x) = 3x^2 - 3x -5$

$r(x) = 28x + 30$

$a_0 = 3x^4 + 3x^3 + 7x^2$

$b_0 = x^2 + 2x + 6$

$a_0 = q_0 b_0 + r_0$

$a_1 = b_0 = x^2 + 2x + 6$

$b_1 = r_0 = 28x + 30$

We will of necessity, in this example, get rational numbers rather than integers.

Now using the same ideas, we will create a function that will determine the gcd of a polynomial.

def my_poly_gcd(A,B): R.<x> = PolynomialRing(QQ) a = A #set the input A equal to a b = B #set the input B equal to b mat = matrix([[0,1],[1,0]]) #create a matrix solution = [] #create a solution vector if (a.degree())>(b.degree()): #determine if the degree of a is greater than the degree of b z = R(a).quo_rem(b) q = z #set q equal to the quotient r = z #set r equal to the remainder mat = mat * matrix([[0,1],[1,-q]]) a = b #replace a with b b = r # replace b with r while r.degree()>0: #while the degree of r is larger than zero z = R(a).quo_rem(b) q = z #set q equal to the new quotient r = z #set r equal to the new remainder mat = mat * matrix([[0,1],[1,-q]]) a = b #replace a with b b = r #replace b with r x = mat[1,0] #set x equal to the [1,0] element in the matrix y = mat[0,0] #set y equal to the [0,0] element in the matrix d = (A * x) + (B * y) #create equation to calculate d solution.append(d) #append d,x,y to the solution vector solution.append(x) solution.append(y) return solution #return the solution vector

Let's test some values of $a$ and $b$ to see if our function runs correctly.

a = 2*x^4 + 6*x^2 + 3*x b = 8*x^3 + 9*x + 1 d = my_poly_gcd(a,b) print d
 Traceback (click to the left of this block for traceback) ... NotImplementedError Traceback (most recent call last): File "", line 1, in File "_sage_input_15.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("YSA9IDIqeF40ICsgNip4XjIgKyAzKngKYiA9IDgqeF4zICsgOSp4ICsgMQpkID0gbXlfcG9seV9nY2QoYSxiKQpwcmludCBk"),globals())+"\\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in File "/tmp/tmpkPzDSR/___code___.py", line 5, in d = my_poly_gcd(a,b) File "/tmp/tmpbZXFvO/___code___.py", line 10, in my_poly_gcd if (a.degree())>(b.degree()): #determine if the degree of a is greater than the degree of b File "sage/structure/element.pyx", line 2880, in sage.structure.element.EuclideanDomainElement.degree (build/cythonized/sage/structure/element.c:22905) NotImplementedError

In theory, this last section of code should work. However, it is telling me that the degree function is throwing an implemented error. I have tried to google how to fix it and cannot figure it out. If it worked, I am sure that my block of code would execute like it is supposed to. I am unsure about what to do with this code at this point.