# Bad Fraction Reduction That Actually Works

$$\frac{16}{64}=\frac{1\rlap{/}6}{\rlap{/}64}=\frac{1}{4}$$

This is certainly not a correct technique for reducing fractions to lowest terms, but it happens to work in this case, and I believe there are other such examples. Is there a systematic way to generate examples of this kind of bad fraction reduction?

• Well $\frac{d}{dx} 2x =2$ by cancelling the $x's$ and the $d$'s – user9413 Jul 5 '11 at 18:37
• @Chandru: While that's not the level I had in mind, that is in the same spirit. – Isaac Jul 5 '11 at 18:38
• I thought this was a bad joke at first, but its actually quite interesting. +1 – Patrick Da Silva Jul 5 '11 at 18:48
• Hum, I also wonder if the systematic way, if it exists, can be extended to be agnostic to base. – Willie Wong Jul 5 '11 at 18:53
• This type of accidental right answer is actually something I try to look for when making up exams for Calculus and other elementary courses. I don't want to waste time arguing with students who "got the right answer" but didn't get any credit for it. – SteveH Jul 5 '11 at 19:04

It's easy to find them all. Suppose $\rm\: (10\ a + n)/(10\ n + b) = a/b\:.\:$ Thus $\rm\ (10\ a-b)\ n = 9\:a\:b\:.$

Case 1: $\rm\:(9,n) = 1\::\ \: 9\ |\ 10\:a-b\ \Rightarrow\ 9\ |\ a-b\ \Rightarrow a=b\ \Rightarrow\ 9\:a\:n = 9\:a^2\ \Rightarrow\ n=a=b\:$ (trivial)

Case 2: $\rm\:(9,n) = 9\::\ 10\:a-b = a\:b\ \Rightarrow\ a|b,\ 10 = (b/a)\:(a+1)\:$ so $\rm\ a,b = 1,5\:$ or $\: 4,8\:$

which yields the solutions: $\:\ 19/95 = 1/5\:,\:$ and $49/98 = 1/2\:.\$ Similar analysis of the remaining

Case 3: $\rm\: (9,n) = 3\::\:$ yields $\:16/64 = 1/4\:,\:$ and $\: 26/65 = 2/5\:.$

• What about for more than 2 digits? – Isaac Jul 5 '11 at 20:31
• A similar analysis should work, but I would look for some optimizations first (which I did not seek above since it was easy enough). – Bill Dubuque Jul 5 '11 at 20:36

Actually this is Project Euler's Problem 33 (in a more general form). In this blog entry it seems a (rather brute force) method is presented to generate your fractions. More examples are $16/64$, $49/98$, $19/95$, and $26/65$. Maybe there is a better way to generate them all, I saw a few promising ones when looking at the solutions on project euler maybe you want to check yourself.

Edit: For bigger numbers you have to say how you allow to cancel terms. For example do you allow $199/995=1/5$ where you cancel two digits or just one digit, do the digits have to be next to each other and so on, also do numerator and denominator need to have the same size or is $39/975=3/75$ allowed too?

• Interestingly, the problem statement says that there are only 4 (non-trivial) such fractions among fractions less than 1 and having 2-digit numerators and denominators (probably the 4 you list). – Isaac Jul 5 '11 at 18:56
• @Listing: The fact cannot be explained using diophantine equations. It is a particularity of these numbers. – Beni Bogosel Jul 5 '11 at 19:37
• @Listing: There are few examples because it's unnatural. The problem doesn't say that there aren't any examples for 3 digit numbers. As suggested, you can make an account on project Euler site and see the implementation made there. Maybe you can generalize it to greater size numbers and see if there are more such examples. – Beni Bogosel Jul 5 '11 at 20:04
• @Beni Sorry you are right, I overread that the numerator is bounded by 2 digits, I think the number $4$ is not that interesting therefore :-). – Listing Jul 5 '11 at 20:39

Prior work on this question can be found in:

Ruekberg, B. Simplified mathematics. Journal of Irreproducible Results 35 (1).

If your institution (scandalously) doesn't carry this journal, a copy can be found here.

Suppose $\frac{AB}{BC} = \frac{A}{C}$ in base $b$, i.e. $C (bA + B) = A (bB + C)$, or $B (A b - C) = A (b-1) C$. We can write $A = x_1 x_2$, $b = 1 + x_3 x_4$, $C = x_5 x_6$ for positive integers $x_1$ to $x_6$
where $B = x_1 x_3 x_5$ and $A b - C = x_2 x_4 x_6$. This leads to the equation $x_5 = \frac{x_1 x_2 (1 + x_3 x_4)}{x_6} - x_2 x_4$. Thus given $x_1$ to $x_4$, $x_6$ should be a divisor of $x_1 x_2 (1 + x_3 x_4)$, $x_5$ is determined by the equation, and we must still ensure $A, B, C$ are all less than $b$. There are lots of solutions, including infinite families. For example, with $x_1 = 2$, $x_2 = 3$, $x_3 = 7m+3$, $x_4 = 2$, $x_5 = 1$ and $x_6 = 12m+6$ (for nonnegative integers $m$) we get $A = 6$, $B = 14m+6$, $C = 12m + 6$ and $b = 14m + 7$.

This can be generalized to give two tests of primality. Consider the equation $$\frac{pa + b}{pb +c} = \frac{a}{c}$$ where $p$, $a$, $b$, and $c$ are all positive integers with $a, b, c < p$. This is a base $p$ version of the question. Suppose that $p$ is some fixed positive integer. We will say that $(a, b, c)$ is a solution if the equation is satisfied. We will say that a solution is trivial if $a = b = c$; otherwise we will say the solution is nontrivial. There are $p -1$ trivial solutions. Check that if $(a, b, c)$ is a solution with any two of $a$, $b$, and $c$ equal then the solution is trivial.

Suppose that $(a, b, c)$ is a nontrivial solution. In this case the greatest common divisor of $b$ and $p - 1$ is greater than $1$. Also the greatest common divisor of $c$ and $p$ is greater than $1$. We can prove two theorems:

Theorem 1 Suppose that $p > 1$ is an integer. Then $p$ is prime if and only if there are no nontrivial solutions.

In one direction this follows from the observation that the greatest common divisor of $c$ and $p$ is greater than $1$. Recall that $c < p$. In the other direction if $p = mn$ then ($n - 1, p - 1, m(n - 1) )$ is a nontrivial solution.

Theorem 2 Suppose that $p > 2$ is an even integer. Then $p - 1$ is prime if and only if and only if in every nontrivial solution $(a, b, c)$ we have $b = p - 1$.

In one direction this follows from the observation that the greatest common divisor of $b$ and $p - 1$ is greater than $1$. In the other direction if $p - 1 = mn$ then $(\frac{1}{2} (m + 1), \frac{1}{2} (m + 1)n, \frac{1}{2} mn)$ is a nontrivial solution.

One can also prove that if $(a, b, c)$ is a nontrivial solution then $2a \leq c < b$. If $p = 4$ the solution $(1, 3, 2)$ shows these limits are the best possible.

One can also prove that the number of notrivial solutions is even unless $p$ is the square of an even integer.

Every issue of the College Mathematics Journal has a column done by Ed Barbeau (the same Barbeau of the Olympiad-style polynomial book, Polynomials) called Fallacies, Flaws, and Flimflam. It very frequently mentions these sorts of oddities, but throughout all of mathematics (like Chandru's $\frac{d}{dx} 2x = 2$).

It's really entertaining. The standard format is for some professor or perhaps high school calculus teacher to write him about something that their students have done that dumbfounded them... and then led to unexpected results. As it's very accessible, I imagine most research institutions should carry the Journal.

T.J. Osler calls these "lucky fractions" in his article; in particular, he shows how other lucky fractions can be constructed from known lucky fractions through their "repetition properties".

To use Isaac's example as the demonstration of the two repetition properties:

$$\frac{16}{64}=\frac{166}{664}=\frac{1666}{6664}=\cdots$$

$$\frac{16}{64}=\frac{1616}{6464}=\frac{161616}{646464}=\cdots$$