aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPaul Duncan <pabs@pablotron.org>2026-01-02 18:27:49 -0500
committerPaul Duncan <pabs@pablotron.org>2026-01-02 18:27:49 -0500
commit34d6b6e6c640c261d622cd3e7ec0964058f1d0b9 (patch)
treec199b38c3c48ac7ad829b4fc4b42db630f52d59b
parent512a56da63a22839bd5828964d0fc4ba7af77832 (diff)
downloadpablotron.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.md17
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 &radic;1013 to
-see if any are a factor of 1013.
+see if any divide 1013.
Unfortunately we don't know &radic;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. &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.
+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&#x2224;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
```
-...
+&nbsp;
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