Mathematical Rules of Thumb, illustrated reader · Chapter 8

08Number Theory

Reduce Large Arithmetic to Small Structure

5 demonstrations follow the chapter's rules. Choose a value, watch the figure and the numbers change, and check your prediction. Every choice is precomputed from the notebook calculations.

Ask the chapter skill

“Help me use Chapter 8 for my question. Choose a rule, check its assumptions, and show how the result changes when an input changes.”

Use math-thumb-number-theory from the companion's skill package. The demonstrations below also work on their own.

Examples use constructed inputs or the book's own values, disclosed in each panel. A picture illustrates a rule; its assumptions set its scope.

1Demonstration 1 of 5

Find an inverse only when arithmetic permits it

Why does a=43 have no inverse modulo 43?

The Euclidean remainder trace leads to the gcd, which decides whether modular division is possible.

a−1(mod⁡m) exists iff gcd⁡(a,m)=1 a^{-1}\pmod m\text{ exists iff }\gcd(a,m)=1

Integer a. Modulus 43. The no-inverse case is explicitly reported rather than divided through.

Predict first. Why does a=43 have no inverse modulo 43?

Choose an example

Find an inverse only when arithmetic permits it. For a=38, gcd(a,43)=1. The inverse is 17, checked by a×inverse mod43=1.
Integer a: 38
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

gcd(a,43)
1
Inverse modulo 43
17

For a=38, gcd(a,43)=1. The inverse is 17, checked by a×inverse mod43=1.

Use the idea

Use rule 8.2.2 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Modulus 43. The no-inverse case is explicitly reported rather than divided through.

Check your understanding: Why does a=43 have no inverse modulo 43?
Every product with 43 is zero modulo 43, so it cannot equal one.

Book source: Rule 8.2.2: Use extended Euclid to find modular inverses. Demonstration C08-D01. Worked illustration.

2Demonstration 2 of 5

Intersect congruences in a small exact search

Why does one solution determine all others modulo fifteen?

Highlight the integers satisfying both congruences and observe repetition every fifteen.

x≡2(mod⁡3),x≡r(mod⁡5) x\equiv2\pmod3,\quad x\equiv r\pmod5

Remainder r modulo 5. Coprime moduli 3 and 5; residues interpreted modulo their respective moduli.

Predict first. Why does one solution determine all others modulo fifteen?

Choose an example

Intersect congruences in a small exact search. The simultaneous conditions x≡2 mod3 and x≡1 mod5 select x≡11 mod15. Because 3 and 5 share no factor, exactly one remainder out of 15 works, so the circled points repeat every 15.
Remainder r modulo 5: 1
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Remainder modulo 3
2
Remainder modulo 5
1
Solution modulo 15
11

The simultaneous conditions x≡2 mod3 and x≡1 mod5 select x≡11 mod15. Because 3 and 5 share no factor, exactly one remainder out of 15 works, so the circled points repeat every 15.

Use the idea

Use rule 8.2.3 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Coprime moduli 3 and 5; residues interpreted modulo their respective moduli.

Check your understanding: Why does one solution determine all others modulo fifteen?
The Chinese remainder theorem gives a unique residue class modulo the product of the coprime moduli.

Book source: Rule 8.2.3: Split coprime congruences with the Chinese remainder theorem. Demonstration C08-D02. Worked illustration.

3Demonstration 3 of 5

Compare counted primes with their asymptotic scale

Does disagreement at n=100 refute asymptotic equivalence?

A real sieve counts primes. The asymptotic curve estimates the scale but does not equal the finite count.

π(n)∼nlog⁡n \pi(n)\sim\frac{n}{\log n}

Sieve upper limit n. Natural logarithm; n/log n is asymptotic and is not an exact finite-n bound.

Predict first. Does disagreement at n=100 refute asymptotic equivalence?

Choose an example

Compare counted primes with their asymptotic scale. The sieve finds 95 primes through 500. n/log n gives 80.4556; the true count is 1.181 times the estimate. The formula promises only that this ratio tends to 1 as n grows. It gets there very slowly and not steadily: from n=100 to n=2000 it wanders between about 1.14 and 1.26.
Sieve upper limit n: 500
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Exact prime count
95
n/log n estimate
80.4556

The sieve finds 95 primes through 500. n/log n gives 80.4556; the true count is 1.181 times the estimate. The formula promises only that this ratio tends to 1 as n grows. It gets there very slowly and not steadily: from n=100 to n=2000 it wanders between about 1.14 and 1.26.

Use the idea

Use rule 8.1.3 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Natural logarithm; n/log n is asymptotic and is not an exact finite-n bound.

Check your understanding: Does disagreement at n=100 refute asymptotic equivalence?
No. Asymptotic equivalence describes the ratio as n tends to infinity, not exact equality at a small n.

Book source: Rule 8.1.3: Estimate prime counts by n over log n. Demonstration C08-D03. Worked illustration.

4Demonstration 4 of 5

Reduce a huge exponent by the period of the powers

What is 10²³ mod 11 without multiplying?

Powers of a number mod 11 must eventually return to 1, then repeat. Find that period and you can throw away whole cycles of the exponent before computing anything.

ak≡akmod⁡d(mod⁡11),d=ord⁡11(a) a^k\equiv a^{k\bmod d}\pmod{11},\quad d=\operatorname{ord}_{11}(a)

Base a. Prime modulus 11, bases coprime to 11, exponent 23. Fermat guarantees the period divides 10.

Predict first. What is 10²³ mod 11 without multiplying?

Choose an example

Reduce a huge exponent by the period of the powers. The powers of 3 repeat every 5 steps, so only the exponent mod 5 matters. 23 mod 5 = 3, so 3²³ ≡ 5 mod 11 without computing a 23-fold product. Fermat's exponent 10 also works, because 5 divides 10, but the true period is shorter.
Base a: 3
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Base a
3
Period (order of a mod 11)
5
23 mod period
3
3²³ mod 11
5

The powers of 3 repeat every 5 steps, so only the exponent mod 5 matters. 23 mod 5 = 3, so 3²³ ≡ 5 mod 11 without computing a 23-fold product. Fermat's exponent 10 also works, because 5 divides 10, but the true period is shorter.

Use the idea

Use rule 8.3.3 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Prime modulus 11, bases coprime to 11, exponent 23. Fermat guarantees the period divides 10.

Check your understanding: What is 10²³ mod 11 without multiplying?
10≡−1 mod 11, so its powers alternate 10, 1. The exponent 23 is odd, giving 10.

Book source: Rule 8.3.3: Reduce modular exponents using the group period. Demonstration C08-D04. Worked illustration.

5Demonstration 5 of 5

See why trial division can stop at the square root

Do you need to test 11 to decide whether 97 is prime?

Divisors come in pairs d and n/d that mirror across the line d=n/d. One partner of every pair is at most √n, so checking small divisors finds every factor.

d∣n⇒min⁡(d,n/d)≤n d\mid n\ \Rightarrow\ \min(d,n/d)\le\sqrt n

Integer n. Positive integers; trial divisors 2 through ⌊√n⌋. Fast for one number, not for many (use a sieve then).

Predict first. Do you need to test 11 to decide whether 97 is prime?

Choose an example

See why trial division can stop at the square root. Every divisor d of 97 comes with a partner 97/d, and one of the two is at most √97≈9.849. So testing 2 through 9 (8 trials) is enough: none divides 97, so 97 is prime. Testing past √n would only find partners of divisors already ruled out.
Integer n: 97
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

n
97
√n
9.84886
Divisors found
2
Trial divisors needed (2 to ⌊√n⌋)
8
Prime
True

Every divisor d of 97 comes with a partner 97/d, and one of the two is at most √97≈9.849. So testing 2 through 9 (8 trials) is enough: none divides 97, so 97 is prime. Testing past √n would only find partners of divisors already ruled out.

Use the idea

Use rule 8.3.1 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Positive integers; trial divisors 2 through ⌊√n⌋. Fast for one number, not for many (use a sieve then).

Check your understanding: Do you need to test 11 to decide whether 97 is prime?
No. 11 > √97 ≈ 9.85, so any factor 11 or larger would have a partner below 9.85, which the trials 2 to 9 already ruled out.

Book source: Rule 8.3.1: Test divisors only through the square root. Demonstration C08-D05. Worked illustration.

Bring the idea to a question of your own

Choose the relationship that answers your question, check its conditions, and compare the result with the accuracy or decision threshold you need.

The chapter skill can adapt these calculations to your inputs. It should name the assumptions, explain what the result supports, and say what still needs evidence. The chapter workbook adds a lab and three exercises with answers.