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
|
---
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 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 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:
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
divide 1013.
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
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∤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 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
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∤1013.
1013 does not have any odd prime factors in the range \[3,√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 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
"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"
|
