--- slug: new-years-primality-testing-by-hand title: "New Year's Primality Testing by Hand" date: "2026-01-02T09:37:22-05:00" --- 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 factors of odd composites are always odd, and we know it is prime because of the [fundamental theorem of arithmetic][]). So our approach will be to check odd primes from 3 to √1013 to see if any divide 1013. Unfortunately we don't know √1013. Fortunately 1013 is close to 1024, and 1024 is even power of 2. So let's use 1024 to approximate √1013: 1. 1013 < 1024, so √1013 < √1024 2. √1024 = √(2{{}}) = 2{{}} = 32 3. Therefore √1013 < 32 So we need to test odd primes in the range \[3,31\] to see if any divide 1013. Before that, though, we prune the list of potential factors with the [divisibility rules][]. We remove: - 3, because the sum of the digits of 1013 isn't divisible by 3: `1+1+3=5` and 3∤5 - 5, because the last digit of 1013 isn't 0 or 5. - 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. - ...and so on for [11][], [13][], [17][], [19][], [23][], and [29][]. (I didn't remember the [divisibility rules][] for the range \[11,29\], so I checked if any of the primes divide 1013 instead). 31 is the only remaining potential factor after pruning. To check it, we can either use the [Euclidean algorithm][] to see if `gcd(31, 1013) != 1` or do some trial 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 with [SymPy][]: ```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 (Wikipedia)" [divisibility rules]: https://en.wikipedia.org/wiki/Divisibility_rule "shorthand rules for determining if one number divides another (Wikipedia)" [11]: https://en.wikipedia.org/wiki/Divisibility_rule#11 "divisibility rules for 11 (Wikipedia)" [13]: https://en.wikipedia.org/wiki/Divisibility_rule#13 "divisibility rules for 13 (Wikipedia)" [17]: https://en.wikipedia.org/wiki/Divisibility_rule#17 "divisibility rules for 17 (Wikipedia)" [19]: https://en.wikipedia.org/wiki/Divisibility_rule#19 "divisibility rules for 19 (Wikipedia)" [23]: https://en.wikipedia.org/wiki/Divisibility_rule#23 "divisibility rules for 23 (Wikipedia)" [29]: https://en.wikipedia.org/wiki/Divisibility_rule#29 "divisibility rules for 29 (Wikipedia)" [euclidean algorithm]: https://en.wikipedia.org/wiki/Euclidean_algorithm "Euclidean Algorithm (Wikipedia)" [integer factorization]: https://en.wikipedia.org/wiki/Integer_factorization "Integer factorization (Wikipedia)" [primality test]: https://en.wikipedia.org/wiki/Primality_test "Primality test (Wikipedia)" [sieve of eratosthenes]: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes "Sieve of Eratosthenes (Wikipedia)" [sympy]: https://sympy.org/ "Python library for symbolic mathematics."