Calculator for Math Theorems

Inspiration

This was a project inspired by the course MATH 135 at UW. There were many times during this course in which I scoured the web for calculators that could verify my work. Unfortunately, none stood out to me. Hence, armed with the knowledge of the key theorems taught in class, I built this project so that others can access this quality-of-life tool.

How it works

Prerequisite (s):

• DIC (divisibility of integer combinations)
• Definition of greatest common divisor

One of the most fundamental properties in MATH 135 was the GCD, or greatest common divisor. This property was used later in the course as part of the proof of many theorems such as the existence of solutions in linear diophantine equations or linear congruences. Particulary, there is a theorem for calculating the gcd of two numbers a, b. The proposition is called GCD with Remainders and proceeds as follows.

(GCD With Remainders (GCD WR))
For all integers a, b, q and r, if a = qb + r, then gcd(a, b) = gcd(b, r).

Proof:

Let a, b, q, r be integers. Assume that a = qb + r. This means that either a and b are both 0 or not both 0. We thus consider these two cases seperately.

Case 1 a = b = 0:

This means that 0 = 0 + r, hence r = 0.
Therefore, gcd(a, b) = gcd(0, 0) = 0 = gcd(b, r)

Case 2 a and b not both 0

Let d = gcd(a, b)
By definition of gcd, d | a and d | b
d | (a(1) + b(-q)) (DIC)
Recall a = qb + r --> r = a - qb
This means that d | r
Let c, an integer, be a common divisor of b and r
Since c | r and c | b --> c | (qb + r) (DIC)
Recall a = qb + r --> c | a
Since c | a and c | b and d = gcd(a, b) --> by definition of gcd, c <= d
Hence, gcd(a, b) = gcd(b, r)

Since gcd(a, b) always invokes itself, we can implement a recursive implementaion of gcd(a, b) in python:

def gcd(a, b):
    a = abs(a)
    b = abs(b)
    if a == 0 and b == 0:
        return 0
    elif a == 0 or b == 0:
        return max(a, b)
    
    return gcd(b, a % b)

Extras

Below is an example of solving a linear diophatine equation.

Click HERE to view the site.