Solution: Factor Microsoft’s Zip Code

The factorization is 3 * 137 * 223.  This number (91653) is small enough to factor by trial devision, an easy-to-program algorithm which checks for divisibility by primes below the square root of the number being factored.

A hand computation, after finding 91653 = 3 * 30551 but no other small divisors, can try to express 30551 as a difference of squares (Fermat's method).  The equation (*)

30551 = x^2 - y^2

with x and y integers, implies x >= sqrt(30551) > 174.  Looking at (*) modulo 3 and modulo 8. we find x is divisible by 12, so x in {180, 192, 204, ....}.  We find the solution 30551 = 32400 - 1849 = 180^2 - 43^2 = (180 + 43)*(180 - 43) = 223 * 137.    

[Vertically align columns for each prime]

(1)      7^2 + n =  30600 =      2^3 * 3^2 * 5^2 *                    17^1

(2)     18^2 + n =  30875 =                  5^3 *             13^1 *      * 19^1

(3)     57^2 + n =  33800 =      2^3 *       5^2 *             13^2

(4)     79^2 - n = -24310 = -1 * 2^1 *       5^1 *      11^1 * 13^1 * 17^1

(5)    107^2 + n =  42000 =      2^4 * 3^1 * 5^3 * 7^1 

(6)    167^2 - n =  -2662 = -1 * 2^1 *                  11^3   

(7)    174^2 - n =   -275 = -1 *             5^2 *      11^1   

(8)    176^2 - n =    425 =                  5^2 *                    17^1

This data was chosen so that:

• All left sides are squares, plus or minus 30551.
• All prime factors on the right side are at most 19.  We treat -1 as a prime.

If we multiply the three equations:

(3)     57^2 + n =  33800 =      2^3 *       5^2 *             13^2

(6)    167^2 - n =  -2662 = -1 * 2^1 *                  11^3   

(7)    174^2 - n =   -275 = -1 *             5^2 *      11^1

then all exponents on the right side are even.  That is, each prime occurs

an even number of times. We conclude:

(57 * 167 * 174)^2 == (-1 * 2^2 * 5^2 * 11^2 * 13)^2

Expand the products to get 1656306^2 == 157300^2 (mod n). That is, 30551 divides 1656306^2 - 157300^2 = (1656306 + 157300) * (1656306 - 157300)  =  1813606 * 1499006.

The Euclidean algorithm reveals GCD(30551, 1813606) = 137 and GCD(30551, 1499006) = 223. The factors of 30551 are 137 and 223.   Both are prime. The full factorization of 98052-6399 is 3 * 137 * 223. If we had instead chosen the subset:

(1)      7^2 + n =  30600 =      2^3 * 3^2 * 5^2 *                    17^1

(3)     57^2 + n =  33800 =      2^3 *       5^2 *             13^2

(8)    176^2 - n =    425 =                  5^2 *                    17^1

then we wouldn’t have been as lucky.  Although the product on the right is a square, the multiplication would give

(7 * 57 * 176)^2 == (2^3 * 3 * 5^3 * 13 * 17)^2     (mod n) .

The next step would reveal:

30551 divides 663000^2 - 70224^2 = (663000 - 70224) * (663000 + 70224) = 593776 * 733224

However, GCD(30551, 593776) = 1 and GCD(30551, 733224) = 30551.

This gives a trivial factorization 30551 = 1*30551.