--- slug: new-years-primality-testing-by-hand title: "New Year's Primality Testing by Hand" date: "2026-01-02T09:37:22-05:00" draft: true --- Happy New Year! The number 2026 has two factors: 2 and 1013. I wondered "is 1013 prime?" and "for fun, can I solve this in my head?" (e.g. no calculator, computer, or pen and paper). If 1013 is *not* prime, then it is composite and must have at least one odd prime factor ≤ ⌊√1013⌋. (We know the factor -- if it exists -- is odd because the factors of odd composite numbers are always odd, and we know the factor is prime because of the [fundamental theorem of arithmetic][]). So our approach will be to check the odd primes from 3 to √1013 to see if any are a factor of 1013. Unfortunately we don't know √1013, so we can't calculate the range upper bound. Fortunately 1013 is close to 1024. 1024 is a handy power of 2, so lets use that instead: 2. √1024 = √(2{{}}) = 2{{}} = 32 3. 1013 < 1024, so √1013 < √1024 4. Therefore, √1013 < 32 So we need to test the odd primes in the range \[3,31\] to see if any are a factor of 1013. Before that, though, we narrow the list with the [divisibility rules][]: 1. Remove 3 because the sum of the digits of 1013 isn't divisible by 3: `1+1+3=5` and 3∤5 2. Remove 5 because the last digit of 1013 isn't 0 or 5. 3. Remove 7 because 5 times the last digit (3) plus the rest (101) is not a multiple of 7: `5*3+101=116, 5*6+11=41`, and 7∤41. 4. ...and so on for [11][], [13][], [17][], [19][], [23][], and [29][]. (Full disclosure: I don't have the [divisibility rules][] for primes in the range \[11,29\] memorized; instead I checked to see if they were factors of 1013). The only remaining possibility is 31. To check it, we can use the [Euclidean algorithm][] to check if `gcd(31, 1013) != 1` or do some brief arithmetic. I chose the latter: 1. 31 = (30 + 1) 2. (30 + 1) * 33 = 990 + 33 = 1023 3. The closest multiples of 31 are 992 and 1023, so 31∤1013. 1013 does not have any odd prime factors in the range \[3,√1013\], so it must be prime. Let's check our work: ```python >>> import sympy >>> sympy.ntheory.primetest.isprime(1013) True ``` ... Success! Further reading: - [Integer factorization][] - [Primality test][] - [Sieve of Eratosthenes][] [fundamental theorem of arithmetic]: https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic "Fundamental Theorem of Arithmetic" [divisibility rules]: https://en.wikipedia.org/wiki/Divisibility_rule "shorthand rules for determining if a number is factor of another number without performing division" [11]: https://en.wikipedia.org/wiki/Divisibility_rule#11 "divisibility rules for 11" [13]: https://en.wikipedia.org/wiki/Divisibility_rule#13 "divisibility rules for 13" [17]: https://en.wikipedia.org/wiki/Divisibility_rule#17 "divisibility rules for 17" [19]: https://en.wikipedia.org/wiki/Divisibility_rule#19 "divisibility rules for 19" [23]: https://en.wikipedia.org/wiki/Divisibility_rule#23 "divisibility rules for 23" [29]: https://en.wikipedia.org/wiki/Divisibility_rule#29 "divisibility rules for 29" [euclidean algorithm]: https://en.wikipedia.org/wiki/Euclidean_algorithm "Euclidean Algorithm" [integer factorization]: https://en.wikipedia.org/wiki/Integer_factorization "Integer factorization" [primality test]: https://en.wikipedia.org/wiki/Primality_test "Primality test" [sieve of eratosthenes]: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes "Sieve of Eratosthenes"