Quick Divisibility Test for Primes up to 67

While there’s known divisibility tests for certain primes (see my notes), the following test very quickly determines if a number is divisible by any prime up to 67 by hand! The original method is due to John Conway, and I learned it from Arthur Benjamin.

Here’s a sample problem along with explanation:

63779 is the product of three primes, each less than 71. Determine their sum.

We set up the equation 63779=pqr, where p, q, and r are primes.

We begin by finding the factor of 2000 closest to 63, namely 64,000. We can therefore rewrite this as

221=2000\cdot 32-63,779.

We can quickly determine that since 2, 5\mid 2000 and 2, 5\nmid 221, 2, 5\nmid 63,779. We now add 32, the quotient in the divisibility above to both sides of the equation to produce:

253=2001\cdot 32-63,779.

Notice the factor of 32 and the left hand side have both increased, while our original number, 63779 has remained the same. Now, as any good contest math student should have the years close to the current year memorized, we know 2001=3\cdot 23\cdot 29. Therefore 3\mid 63779\iff 3\mid 253, however, 3\nmid 253. Similarly 23\mid 63779\iff 23\mid 253. This time, 253=23\cdot 11, therefore 23\mid 63779. We’ve found one prime divisor: p=23.

We could now divide 63779 by 23, however, this gives the equation 2773=qr, and we don’t have any better ideas for how to factorize 2773. Therefore, instead, we’ll use the prime factorizations of some other numbers close to 2000:

1998=2\cdot 3^3\cdot 37,   2002=2\cdot 7\cdot 11\cdot 13,   2006=2\cdot 17\cdot 59,   2009=41\cdot 49

and 2010=2\cdot 3\cdot 5\cdot 67,2013=3\cdot 11\cdot 61, 2015=5\cdot 13\cdot 31, 2021=43\cdot 47.

For instance, to determine if our number is divisible by 37, we would take the original equation and subtract 2\cdot 32 to produce 157=1998\cdot 32-63,779. Then, we know 37\mid 63779\iff 37\mid 157, however, clearly 37\nmid 157.

Similarly, to test if our number is divisible by 7, 11, or 13, we simply add 2\cdot 32 to our original equation to produce 285=2002\cdot 32-63779. Therefore, again 11\mid 285\iff 11\mid 63779, however, clearly 11\nmid 285, hence the same is true for 63779.

Next, to determine if the original number is divisible by 17 or 59, we add 6\cdot 32 to our original equation (or more simply, 4\cdot 32 to the equation in the last paragraph) to get

413=2006\cdot 32-63779.

Since 2006=2\cdot 17\cdot 59, we see 17\mid 413\iff 17\mid 63779, however, clearly 17\nmid 413. Similarly, 59\mid 413\iff 59\mid 63779. Now since 420=60\cdot 7, we see 413=59\cdot 7, hence 59\mid 413, and 59\mid 63779. We’ve therefore found a second prime factor: q=59.

At this point that we have two prime factors, we could continue on with our test, but we have a pretty good idea of what the third factor is by division: 63779=23\cdot 59\cdot r. One way to quickly compute this in our heads would be to notice

59\cdot 23=(60-1)(20+3)=1200+180-20-3=1357.

Since we know r is an integer, we attempt to bound it. We know r=\frac{63779}{1357}. We notice 40\cdot 1357=52480, while 50\cdot 1357=67850, therefore, 40<r<50.  We then subtract 40 from both sides of our equation:


While we could compute the numerator mentally, since we know 1\le r-40\le 9, we know it must be a single numerical digit! We therefore just consider the unit digit of the numerator which is 9. Since we’re dividing by a number which ends in 7, we know r-40 must be 7, since 7\cdot 7\equiv 49\equiv 9\pmod{10}. Therefore r=47.

Hence our desired sum is p+q+r=23+59+47=\boxed{129}.

Alternatively, we could verify 47\mid 63779 using the prime factorization of next year, 2021. I’ll leave this as an exercise for anyone interested.

While this method isn’t super practical, I think it’s interesting that you can essentially compute prime factors up to 67 with a quick trick in your head. The most difficult part is memorizing the prime factorizations of the numbers close to 2000, but hopefully this is familiar for any seasoned contest mathematician (who might be interested in using this).

References: Arthur Benjamin, Factoring Numbers with Conway’s 150 Method
The College Mathematics Journal, Vol. 49, No. 2, pp. 122-125, March 2018.

Similar to Fermat’s Last Theorem

Let n be a positive integer. Prove that there exist distinct positive integers x, y, z such that x^{n-1} + y^n = z^{n+1}. (Source: 1997 IMO Shortlist N6)

The equation x^{n}+y^n=z^n is known to have no nontrivial solutions for n\ge 3 due to Fermat’s Last Theorem (if you’ve not read Fermat’s Enigma I highly recommend checking it out). This very similar looking equation, however, has an infinite number of solutions. In this blog post, we’ll examine how this difficult looking problem can be solved with one simple observation: 1+8=9.

For a concrete example of this, consider the case n=3 giving the equation x^{2}+y^{3}=z^{4}. Assume we multiply the equation by a number of the form $2^{\alpha}\cdot 3^{\beta}$.  We then will have: $$2^{\alpha}\cdot 3^{\beta}+2^{\alpha+3}\cdot 3^{\beta}=2^{\alpha}\cdot 3^{\beta+2}.$$ Since we want the first part to be a perfect square, we should have $2\mid \alpha$ and $2\mid \beta$. Since the second part should be a perfect cube, we should have $3\mid (\alpha+3)$ and $3\mid \beta$. Finally, since the last part should be a perfect fourth power, $4\mid \alpha$ and $4\mid (\beta+2)$. Solving these system of linear congruences gives $\alpha=0$ and $\beta=6$! We get back the equation $3^6+3^6\cdot 2^3=3^8$, from which we read off the solution $(x,y,z)=(3^3, 3^2\cdot 2, 3^2)=(27, 18, 9)$

We now attempt to generalize this technique. We begin by multiplying 1+8=9 by 2^{\alpha}\cdot 3^{\beta} again to obtain 2^{\alpha}\cdot 3^{\beta}+2^{\alpha+3}\cdot 3^{\beta}=2^{\alpha}\cdot 3^{\beta+2}. We then want the exponents on the leftmost term to be divisible by n, on the middle term to be divisible by n+1, and on the rightmost term to be divisible by n+2. This is equivalent to:

\begin{cases} \alpha&\equiv 0\pmod{n} \\ \alpha&\equiv -3\pmod{n+1} \\ \alpha&\equiv 0\pmod{n+2} \end{cases}   and    \begin{cases} \beta&\equiv 0\pmod{n} \\ \beta&\equiv 0\pmod{n+1} \\ \beta&\equiv -2\pmod{n+2}. \end{cases}

Notice that in the first case, the first and third conditions are equivalent to \alpha\equiv 0\pmod{n(n+2)}. Since \gcd(n, n+2)=\gcd(n+1, n+2)=1, we can use the Chinese Remainder Theorem to know that \alpha has a unique solution mod \text{lcm}(n, n+1, n+2)

On the other hand, for \beta, in the case that n is even, \gcd(n, n+2)=2, therefore, we have to use an extended version of the Chinese Remainder Theorem. Thankfully, since \gcd(n, n+2)=2 in this case and 0\equiv -2\pmod{2}, we are still guaranteed a unique solution for \beta mod \text{lcm}(n, n+1, n+2).

Substituting these solutions in for \alpha and \beta gives a solution (x,y,z) to the original equation. Once we have the congruences for \alpha and \beta, we can then find an infinite parameterized version of solutions for (x,y,z).

For instance, in the case of n=3 above, we had \alpha\equiv 0\pmod{12}, \beta\equiv 6\pmod{12}. If we in general write \alpha=12\alpha' and \beta=12\beta'+6, we then find

2^{12\alpha'}\cdot 3^{12\beta'+6}+2^{12\alpha'+3}\cdot 3^{12\beta'+6}=2^{12\alpha'}\cdot 3^{12\beta'+8}.

This then translates into (x,y,z)=(2^{6\alpha'}\cdot 3^{6\beta'+3}, 2^{4\alpha'+1}\cdot 3^{2+4\beta'}, 2^{3\alpha'}\cdot 3^{3\beta'+2}). Notice for \alpha'=\beta'=0, this gives the solution triple (x,y,z)=(27, 18, 9) found above. 

It’s pretty interesting to me how when you change one small thing in the formulation of the problem (subtract 1 from the exponent on x and add 1 to the exponent of z) gives an entirely new problem, where we go from no solutions to an infinite number!