Quadratic Reciprocity for Engineers

After one of my more freewheeling evening office hours at the Tatkon Center, I found myself trying to explain why quadratic reciprocity is so cool to some engineering students (mostly in their first year) who had no special background in number theory or abstract algebra. For me, quadratic reciprocity was one of the first results in mathematics that I felt was surprising, which wasn't "obvious" like the results I had seen in calculus. But I encountered it in the context of a course and after a considerable amount of prior exposure. Could I nonetheless give some hint as to why someone might care? Why it might be interesting, powerful, puzzling, or even beautiful?

It was more challenging than I expected, but here is the idea that I ended up with, after many false starts and feedback from my patient and enthusiastic audience. I found myself telling a similar story a few more times over the years, so I thought it might be fun to put up a quick, accessible version with an accompanying Python script.

The Setup

Suppose that we look at the prime factorizations of numbers of the form n² - 5 for a bunch of n, which we can do so by running the following simple script.

import math

def prime_factors(n):
    """Return the list of prime factors of the positive integer n in ascending order"""
    if n <= 1:
        return []
    elif n % 2 == 0:
        return [2] + prime_factors(n/2)
    else:
        for d in list(range(3, int(n+1), 2)):
            if n % d == 0:
                return [d] + prime_factors(n/d)

def f(n):
    return n*n - 5

for n in range(1, 200):
    print("f(%d) = %d : " % (n, f(n)), prime_factors(f(n)))

The output of the program is given below. Is there anything you notice about the prime factors, which are listed in the square brackets ("[,]") on the right?

f(1) = -4 :  []
f(2) = -1 :  []
f(3) = 4 :  [2, 2]
f(4) = 11 :  [11]
f(5) = 20 :  [2, 2, 5]
f(6) = 31 :  [31]
f(7) = 44 :  [2, 2, 11]
f(8) = 59 :  [59]
f(9) = 76 :  [2, 2, 19]
f(10) = 95 :  [5, 19]
f(11) = 116 :  [2, 2, 29]
f(12) = 139 :  [139]
f(13) = 164 :  [2, 2, 41]
f(14) = 191 :  [191]
f(15) = 220 :  [2, 2, 5, 11]
f(16) = 251 :  [251]
f(17) = 284 :  [2, 2, 71]
f(18) = 319 :  [11, 29]
f(19) = 356 :  [2, 2, 89]
f(20) = 395 :  [5, 79]
f(21) = 436 :  [2, 2, 109]
f(22) = 479 :  [479]
f(23) = 524 :  [2, 2, 131]
f(24) = 571 :  [571]
f(25) = 620 :  [2, 2, 5, 31]
f(26) = 671 :  [11, 61]
f(27) = 724 :  [2, 2, 181]
f(28) = 779 :  [19, 41]
f(29) = 836 :  [2, 2, 11, 19]
f(30) = 895 :  [5, 179]
f(31) = 956 :  [2, 2, 239]
f(32) = 1019 :  [1019]
f(33) = 1084 :  [2, 2, 271]
f(34) = 1151 :  [1151]
f(35) = 1220 :  [2, 2, 5, 61]
f(36) = 1291 :  [1291]
f(37) = 1364 :  [2, 2, 11, 31]
f(38) = 1439 :  [1439]
f(39) = 1516 :  [2, 2, 379]
f(40) = 1595 :  [5, 11, 29]
f(41) = 1676 :  [2, 2, 419]
f(42) = 1759 :  [1759]
f(43) = 1844 :  [2, 2, 461]
f(44) = 1931 :  [1931]
f(45) = 2020 :  [2, 2, 5, 101]
f(46) = 2111 :  [2111]
f(47) = 2204 :  [2, 2, 19, 29]
f(48) = 2299 :  [11, 11, 19]
f(49) = 2396 :  [2, 2, 599]
f(50) = 2495 :  [5, 499]
f(51) = 2596 :  [2, 2, 11, 59]
f(52) = 2699 :  [2699]
f(53) = 2804 :  [2, 2, 701]
f(54) = 2911 :  [41, 71]
f(55) = 3020 :  [2, 2, 5, 151]
f(56) = 3131 :  [31, 101]
f(57) = 3244 :  [2, 2, 811]
f(58) = 3359 :  [3359]
f(59) = 3476 :  [2, 2, 11, 79]
f(60) = 3595 :  [5, 719]
f(61) = 3716 :  [2, 2, 929]
f(62) = 3839 :  [11, 349]
f(63) = 3964 :  [2, 2, 991]
f(64) = 4091 :  [4091]
f(65) = 4220 :  [2, 2, 5, 211]
f(66) = 4351 :  [19, 229]
f(67) = 4484 :  [2, 2, 19, 59]
f(68) = 4619 :  [31, 149]
f(69) = 4756 :  [2, 2, 29, 41]
f(70) = 4895 :  [5, 11, 89]
f(71) = 5036 :  [2, 2, 1259]
f(72) = 5179 :  [5179]
f(73) = 5324 :  [2, 2, 11, 11, 11]
f(74) = 5471 :  [5471]
f(75) = 5620 :  [2, 2, 5, 281]
f(76) = 5771 :  [29, 199]
f(77) = 5924 :  [2, 2, 1481]
f(78) = 6079 :  [6079]
f(79) = 6236 :  [2, 2, 1559]
f(80) = 6395 :  [5, 1279]
f(81) = 6556 :  [2, 2, 11, 149]
f(82) = 6719 :  [6719]
f(83) = 6884 :  [2, 2, 1721]
f(84) = 7051 :  [11, 641]
f(85) = 7220 :  [2, 2, 5, 19, 19]
f(86) = 7391 :  [19, 389]
f(87) = 7564 :  [2, 2, 31, 61]
f(88) = 7739 :  [71, 109]
f(89) = 7916 :  [2, 2, 1979]
f(90) = 8095 :  [5, 1619]
f(91) = 8276 :  [2, 2, 2069]
f(92) = 8459 :  [11, 769]
f(93) = 8644 :  [2, 2, 2161]
f(94) = 8831 :  [8831]
f(95) = 9020 :  [2, 2, 5, 11, 41]
f(96) = 9211 :  [61, 151]
f(97) = 9404 :  [2, 2, 2351]
f(98) = 9599 :  [29, 331]
f(99) = 9796 :  [2, 2, 31, 79]
f(100) = 9995 :  [5, 1999]
f(101) = 10196 :  [2, 2, 2549]
f(102) = 10399 :  [10399]
f(103) = 10604 :  [2, 2, 11, 241]
f(104) = 10811 :  [19, 569]
f(105) = 11020 :  [2, 2, 5, 19, 29]
f(106) = 11231 :  [11, 1021]
f(107) = 11444 :  [2, 2, 2861]
f(108) = 11659 :  [89, 131]
f(109) = 11876 :  [2, 2, 2969]
f(110) = 12095 :  [5, 41, 59]
f(111) = 12316 :  [2, 2, 3079]
f(112) = 12539 :  [12539]
f(113) = 12764 :  [2, 2, 3191]
f(114) = 12991 :  [11, 1181]
f(115) = 13220 :  [2, 2, 5, 661]
f(116) = 13451 :  [13451]
f(117) = 13684 :  [2, 2, 11, 311]
f(118) = 13919 :  [31, 449]
f(119) = 14156 :  [2, 2, 3539]
f(120) = 14395 :  [5, 2879]
f(121) = 14636 :  [2, 2, 3659]
f(122) = 14879 :  [14879]
f(123) = 15124 :  [2, 2, 19, 199]
f(124) = 15371 :  [19, 809]
f(125) = 15620 :  [2, 2, 5, 11, 71]
f(126) = 15871 :  [59, 269]
f(127) = 16124 :  [2, 2, 29, 139]
f(128) = 16379 :  [11, 1489]
f(129) = 16636 :  [2, 2, 4159]
f(130) = 16895 :  [5, 31, 109]
f(131) = 17156 :  [2, 2, 4289]
f(132) = 17419 :  [17419]
f(133) = 17684 :  [2, 2, 4421]
f(134) = 17951 :  [29, 619]
f(135) = 18220 :  [2, 2, 5, 911]
f(136) = 18491 :  [11, 41, 41]
f(137) = 18764 :  [2, 2, 4691]
f(138) = 19039 :  [79, 241]
f(139) = 19316 :  [2, 2, 11, 439]
f(140) = 19595 :  [5, 3919]
f(141) = 19876 :  [2, 2, 4969]
f(142) = 20159 :  [19, 1061]
f(143) = 20444 :  [2, 2, 19, 269]
f(144) = 20731 :  [20731]
f(145) = 21020 :  [2, 2, 5, 1051]
f(146) = 21311 :  [101, 211]
f(147) = 21604 :  [2, 2, 11, 491]
f(148) = 21899 :  [61, 359]
f(149) = 22196 :  [2, 2, 31, 179]
f(150) = 22495 :  [5, 11, 409]
f(151) = 22796 :  [2, 2, 41, 139]
f(152) = 23099 :  [23099]
f(153) = 23404 :  [2, 2, 5851]
f(154) = 23711 :  [131, 181]
f(155) = 24020 :  [2, 2, 5, 1201]
f(156) = 24331 :  [29, 839]
f(157) = 24644 :  [2, 2, 61, 101]
f(158) = 24959 :  [11, 2269]
f(159) = 25276 :  [2, 2, 71, 89]
f(160) = 25595 :  [5, 5119]
f(161) = 25916 :  [2, 2, 11, 19, 31]
f(162) = 26239 :  [19, 1381]
f(163) = 26564 :  [2, 2, 29, 229]
f(164) = 26891 :  [26891]
f(165) = 27220 :  [2, 2, 5, 1361]
f(166) = 27551 :  [27551]
f(167) = 27884 :  [2, 2, 6971]
f(168) = 28219 :  [28219]
f(169) = 28556 :  [2, 2, 11, 11, 59]
f(170) = 28895 :  [5, 5779]
f(171) = 29236 :  [2, 2, 7309]
f(172) = 29579 :  [11, 2689]
f(173) = 29924 :  [2, 2, 7481]
f(174) = 30271 :  [30271]
f(175) = 30620 :  [2, 2, 5, 1531]
f(176) = 30971 :  [30971]
f(177) = 31324 :  [2, 2, 41, 191]
f(178) = 31679 :  [79, 401]
f(179) = 32036 :  [2, 2, 8009]
f(180) = 32395 :  [5, 11, 19, 31]
f(181) = 32756 :  [2, 2, 19, 431]
f(182) = 33119 :  [33119]
f(183) = 33484 :  [2, 2, 11, 761]
f(184) = 33851 :  [33851]
f(185) = 34220 :  [2, 2, 5, 29, 59]
f(186) = 34591 :  [34591]
f(187) = 34964 :  [2, 2, 8741]
f(188) = 35339 :  [35339]
f(189) = 35716 :  [2, 2, 8929]
f(190) = 36095 :  [5, 7219]
f(191) = 36476 :  [2, 2, 11, 829]
f(192) = 36859 :  [29, 31, 41]
f(193) = 37244 :  [2, 2, 9311]
f(194) = 37631 :  [11, 11, 311]
f(195) = 38020 :  [2, 2, 5, 1901]
f(196) = 38411 :  [71, 541]
f(197) = 38804 :  [2, 2, 89, 109]
f(198) = 39199 :  [39199]
f(199) = 39596 :  [2, 2, 19, 521]

Among other things, you may notice that we don't get certain small primes like 3, 7, 13, and 17 that show up, even thought we've computed pretty far. In general, we'll never get prime that appears that ends in 3 or 7.

The Short Explanation

This phenomenon can be explained by quadratic reciprocity. If p is an odd prime dividing n² - 5, its Legendre symbol (5 | p) = 1 and by quadratic reciprocity, 1 = (5 | p) = (p | 5) and so we must have p = 0, 1, 4 (mod 5). In other words, p can't have 3 or 7 as its last digit.