diff options
| author | Paul Duncan <pabs@pablotron.org> | 2026-01-02 18:27:49 -0500 |
|---|---|---|
| committer | Paul Duncan <pabs@pablotron.org> | 2026-01-02 18:27:49 -0500 |
| commit | 34d6b6e6c640c261d622cd3e7ec0964058f1d0b9 (patch) | |
| tree | c199b38c3c48ac7ad829b4fc4b42db630f52d59b | |
| parent | 512a56da63a22839bd5828964d0fc4ba7af77832 (diff) | |
| download | pablotron.org-34d6b6e6c640c261d622cd3e7ec0964058f1d0b9.tar.xz pablotron.org-34d6b6e6c640c261d622cd3e7ec0964058f1d0b9.zip | |
content/posts/2026-01-02-new-years-primality-testing-by-hand.md: s/are a factor of/divide/, other minor wording tweaks
| -rw-r--r-- | content/posts/2026-01-02-new-years-primality-testing-by-hand.md | 17 |
1 files changed, 9 insertions, 8 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 00c13da..c2b24c9 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 @@ -19,20 +19,21 @@ 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. +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 lets use that instead: +of 2, so let's use that instead: 2. √1024 = √(2{{<sup 10>}}) = 2{{<sup 5>}} = 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. +divide 1013. -Before that, though, we narrow the list with the [divisibility rules][]: +Before that, though, we narrow the list of candidates 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 @@ -42,8 +43,8 @@ Before that, though, we narrow the list with the [divisibility rules][]: 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 range \[11,29\] memorized; instead I checked to see if any of them +divide 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 @@ -63,7 +64,7 @@ Let's check our work: >>> sympy.ntheory.primetest.isprime(1013) True ``` -... + Success! @@ -76,7 +77,7 @@ Further reading: [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" + "shorthand rules for determining if one number divides another" [11]: https://en.wikipedia.org/wiki/Divisibility_rule#11 "divisibility rules for 11" [13]: https://en.wikipedia.org/wiki/Divisibility_rule#13 |
