diff options
Diffstat (limited to 'content')
| -rw-r--r-- | content/posts/2026-01-02-new-years-primality-testing-by-hand.md | 51 |
1 files changed, 25 insertions, 26 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 index 502b850..2fd0275 100644 --- 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 @@ -7,47 +7,46 @@ 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, +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][]). +(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 the odd primes from 3 to √1013 to -see if any divide 1013. +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, so we can't calculate the range -upper bound. Fortunately 1013 is close to 1024. 1024 is a handy power -of 2, so let's use that instead: +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{{<sup 10>}}) = 2{{<sup 5>}} = 32 -3. 1013 < 1024, so √1013 < √1024 -4. Therefore, √1013 < 32 +3. Therefore √1013 < 32 -So we need to test the odd primes in the range \[3,31\] to see if any -divide 1013. +So we need to test odd primes in the range \[3,31\] to see if any divide +1013. -Before that, though, we narrow the list of candidates with the -[divisibility rules][]: +Before that, though, we prune the list of potential factors with the +[divisibility rules][]. We remove: -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 +- 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. -4. ...and so on for [11][], [13][], [17][], [19][], [23][], and [29][]. +- ...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 any of them -divide 1013). +(I didn't remember the [divisibility rules][] for the range \[11,29\], +so I checked if any of the primes divide 1013 instead). -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: +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 |