1 files changed, 99 insertions, 0 deletions

diff --git a/content/posts/2026-01-02-new-years-primality-testing-by-hand.md b/content/posts/2026-01-02-new-years-primality-testing-by-hand.md
new file mode 100644
index 0000000..00c13da
--- /dev/null
+++ b/content/posts/2026-01-02-new-years-primality-testing-by-hand.md
@@ -0,0 +1,99 @@
+---
+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. &radic;1024 = &radic;(2{{<sup 10>}}) = 2{{<sup 5>}} = 32
+3. 1013 &lt; 1024, so &radic;1013 &lt; &radic;1024
+4. Therefore, &radic;1013 &lt; 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&#x2224;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&#x2224;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&#x2224;1013.
+
+1013 does not have any odd prime factors in the range \[3,&radic;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"