Number Theory

Relatively Prime Linear Combinations

If there exist x and y for which ax+by=GCD(a,b) then GCD(x,y)=1.

Let g=GCD(a,b) and x and y solutions to ax+by=g.

Since g|a and g|b, there exist integers n and m such that a=gn and b=gm.


So, nx+my=1

The GCD(n,m)=1 since g is the GCD(a,b).

Let d be a divisor of x. If d also divides my, then d must divide 1, which isn’t possible. So, GCD(x,y)=1.

Fraction Sum Divisors

Given a pair of reduced fractions, e.g., `1/30` and `1/42`, or `3/10` and `1/5`, we add them with the LCD Algorithm.

If the sum reduces, then it will reduce by a factor of the GCD of the denominators.

Example `1/30+1/42`

  • Find the LCM
    `30=2 * 3 * 5` and `42=2 * 3 * 7`
    so the LCM `=2 * 3 * 5 * 7 = 210` and the GCD `=2* 3=6`.
  • Modify the first fraction
    `210/30=7` so we rewrite `1/30 = (7*1)/(7*30) = 7/210`
  • Modify the second fraction
    `210/42=5` so `1/42 = (5*1)/(5*42) = 5/210`
  • Combine the fractions with the common denominator
    `1/30+1/42 = 7/210+5/210 = 12/210`
  • Notice if they reduce
    `12/210= (12 -: 6)/(210 -: 6) = 2/35`

Example `11/30+1/42`

`11/30+1/42 = 77/210+5/210 = 82/210= (82 -: 2)/(210 -: 2) = 41/105`


Applying the LCD algorithm `a/c+b/d=(au+bv)/lcm`

Note that the LCM of two numbers is the product of the highest power of each prime from the prime factorizations of the two numbers.

Note that the GCD is the lowest power of the primes common to the two numbers.

These sets of prime factors are disjoint and complementary to the product of the two numbers, i.e.,

`c* d = lcm * gcd `(1)



To apply the LCD Algorithm we need to find `u` and `v`, the complementary factors of the `lcm` for `c` and `d` respectively.

`u=lcm/c` and `v=lcm/d`(3)

Since `u=lcm/c=d/gcd`, then `u` is made from factors of `d` that are not common to `c`. Similarly, `v` is made from factors of `c` that are not common to `d`. Hence `u` and `v` have no common factors, i.e., `GCD(u,v)=1`.

Notice that `u*v = lcm/c * lcm/d` and `gcd=(c*d)/lcm`

Hence, `lcm = gcd * u * v`

so `a/c+b/d=(au+bv)/(gcd * u * v)`

If this sum is reducible, then there exists an Integer `n` such that

`(au+bv)/n` and `(gcd * u * v)/n`

If `n` divides `u` then n must divide `bv`. However, we know that `u` is relatively prime to `v`. Additionally, since `b` is relatively prime to `d`, `b` is also relatively prime to `u`. Hence `n` can’t divide `bv` and then must not divide `u`,

So if `n` is to be the GCD of the numerator and denominator of the sum, it must divide the `GCD(c,d)`.

Fraction Addition and Reducible Sums

Fraction Sum Exploration

A common method for adding fractions is to find the lowest common multiple of the denominators. This is called the LCD algorithm, Lowest Common Denominator. Even though we have the smallest possible denominator that allows us to combine the fractions, sometimes the sum will still reduce. I have always wondered why.

Consider `1/3+1/6`. The LCD = 6, so the sum becomes `2/6+1/6=3/6` or `1/2`. This is reducible.

Now consider `1/3+1/2`. The LCD = 6, so the sum becomes `2/6+3/6=5/6`. This is clearly not reducible.

I finally found an article explaining the theory behind when a fraction sum is reducible or irreducible.

Biscuits of Number Theory by Arthur T. Benjamin, Ezra Brown, 2006, MAA

Originally published as:
Reducing the Sum of Two Fractions
Shultz, Harris S. and Ray C. Shiflett. Mathematics Teacher. vol. 98, no. 7 (March 2005): pp.486-490.

If the denominators have a commom prime power in the prime factorizations, then some sums are reducible, otherwise, the sums are always irreducible. For denominators `12=2^2*3` and `15=3*5` there exist numerators for which the sum will reduce since they have a common prime power of `3^1`, and, for example, `1/12+1/15=9/60 = 3/20`. For denominators `8=2^3` and `12=2^2*3` there are no numerators for which the sum reduces, since they do not have a common prime power. Here I am assuming that the numerators are relatively prime to their denominators, i.e., they have a gcd of 1.

Even better, if the common prime power is based on 2, then the sums are always reducible. Otherwise, there exist numerators for which the sum will reduce. The problem then becomes finding those numerators.

10 vs 5 1 2 3 4
1 3/10 1/2 7/10 9/10
3 1/2 7/10 9/10 11/10
7 9/10 11/10 13/10 3/2
9 11/10 13/10 3/2 17/10

Relatively Prime Integers

`a` and `b` are said relatively prime if `GCD(a,b)=1`.

Euler’s Totient function, `\phi(n)`, counts the number of positive integers less than `n` that are are relatively prime to `n`.

For example, numbers relatively prime to 15 are `{1,2,4,7,8,11,13,14}`, so `\phi(15)=8`.

 1,  2,  3,  4,  5,  6,  7 8,  9, 10, 11, 12, 13, 14

There is always an interesting symmetry to these lists, that is, if `a` is in the list, then `n-a` is in the list.

Take `a<n` and `GCD(a,n)=1`.

Now lets suppose that `n` and `n-a` are not relatively prime, so `GCD(n-a,n)=d>1`.

This means that `d|n` so there exists a `k` where `n=dk`. Similarly, `n-a=dj` for some `j`.

Then `a=n-dj=dk-dj=d(k-j)`, so that `d|a`, contradicting our hypotheses, `GCD(a,n)=1`.

So `d` must me `1`.

This may also be shown using the fact that `a` and `n` are relatively prime, if and only if there exist integers `x` and `y` such that `ax+ny=1`.(ref)

So far, I lack an simpler argument that if `a` is relatively prime to `n` and `a<n` then `n-a` is also.

Some Number Theory Basics

A linear combination theorem about divisors

If `c|a` and `c|b`, then `c|(ax+by)` for arbitrary integers `x` and `y`.

If `c|a` then there exists an integer `n` such that `a=cn`, similarly, `b=cm` for some `m`.

Given any integers `x` and `y`, `ax+by = cnx+cmy = c(nx+my)`. Since `n`, `m`, `x`, and `y` are integers, then so is `nx+my`.

Concerning the gcd of `a` and `b`

Given integers `a` and `b`, there exist integers `u` and `v` such that `au+bv=` gcd`(a,b)`.

Now consider the set `S={ ax+by | ax+by > 0` and `x` and `y` are integers `}`

`S` is non empty since if `y=0`, then `ax+b*0=|a|` if we choose `x` to be `1` or `-1` as necessary. The set `S` must contain some smallest number, say `d`. There exist `u` and `v` such that `d=au+bv`.

Now let’s apply the Division Algorithm. We can find `q` and `r` so that `a=qd+r`, where `0 <= r <= d`.

So, `r = a-qd = a-q(au+bv) = a(1-qu)+b(-qv)`.

Suppose `r` is positive. Then `r` is in `S`. This contradicts the Division Algorithm, since `r<d`. Hence `r=0` and `a=qd`. Now, `d|a` and similarly, `d|b`, so `d` is a common divisor of `a` and `b`.

Take `c` to be any common divisor of `a` and `b`. `c|(au+bv)` and so `c|d`. This implies that `c <= d` and `d` must be the gcd(`a`,`b`).

Now that we know values exist, the Euclidean Algorithm for finding the gcd of two numbers can be used to find values for `u` and `v`.

Linear Combinations of Relatively Prime Integers

`a` and `b` are relatively prime, if and only if there exist integers `x` and `y` such that `ax+by=1`.

Symmetry with Sums of Proper Fractions

If `a` is relatively prime to `b`, then `b-a` is also relatively prime to `b`. (ref)

Consider the sum `a/b+c/d`, where both fractions are reduced, that is, `a` is relatively prime to `b` and `c` is relatively prime to `d`.

Then the sum `(b-a)/b+(d-c)/d` is also the sum of two reduced fractions.


So if `a/b+c/d` is a reducible sum then so is `(b-a)/b+(d-c)/d`. Better yet, their sum is always `2`.