1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
---
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{{<sup 10>}}) = 2{{<sup 5>}} = 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."
|
