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.