I am currently writing yet another rational number class where the fraction should always be normalized. When adding a natural number to a normalized fraction, it possible to get a non-normalized fraction?
In other words, if I compute r2 := r1 + n where r1 is a normalized fraction and n a natural number such as:
numer(r2) := numer(r1) + n * denom(r1)denom(r2) := denom(r1)
With such an algorithm, is it possible to get a fraction r2 that is not already normalized or will r2 always be normalized?
Let $\dfrac{x}{y}$ be a normalized fraction such as $\gcd(x, y) = 1$. We want to prove that adding an integer to a fraction with the naive algorithm produces another normalized fraction (a fraction for which the greatest common divisor of the numerator and denominator equals $1$). The algorithm produces the following fraction:
$\dfrac{x}{y} + n = \dfrac{x + n·y}{y}$
One of the properties of the greatest common divisor is that for any integer $n$:
$\gcd(a + m·b, b) = \gcd(a, b)$
Therefore, we have the following equivalence for our resulting fraction:
$\gcd(x + n·y, y) = \gcd(x, y) = 1$
Therefore, our algorithm to add an integer to a normalized fraction always produces a normalized fraction.