# Chapter 8 notebook: Number Theory: Reduce Large Arithmetic to Small Structure

**Goal:** Reduce integer calculations while preserving divisibility and invertibility.

**Start with:** Rules 8.1.1, 8.2.2, 8.2.3. Use a calculator or the optional Python lab. Programming is optional for the workbook; the Jupyter version requires a Python 3 kernel. All lab numbers are constructed practice inputs, not observed data.

**Source:** [Finished Chapter 8](../skills/math-thumb-number-theory/references/chapter.md) from *Mathematical Rules of Thumb*. Numbered rules, classifications, and the decision path come from the book. The lab, exercises, answer key, and worksheet prompts are companion additions.

## 1. Frame your decision

Write a question in which an answer would change something you do. Gather: Integers and modulus; whether an exact answer or scale estimate is needed; coprimality; one-number versus many-number workload.

- My question and intended decision:
- Known inputs and units:
- Required accuracy or threshold:
- What I expect before calculating:
- What I still need to find out:

Use the lab as a worked starting point if you do not yet have your own problem. For notation or prerequisites, ask the chapter skill to explain only the concept blocking the next step.

## 2. Choose a route

- **Do you need a gcd but not a factorization?** Use the Euclidean algorithm. Record its equations if an inverse or Bézout coefficients may be needed next.
- **Is a complete factorization already known?** Translate exponent choices directly into a divisor count. Do not enumerate divisors unless the list itself is required.
- **Do you need an aggregate prime estimate?** Use $n/\log n$ for scale. If you need exact primes, choose between trial division, a sieve, and a larger-scale primality method based on workload.
- **Is the answer requested modulo $m$?** Reduce throughout addition and multiplication. Before dividing, test invertibility with a gcd.
- **Can the modulus be separated into coprime factors?** Solve the smaller congruences and reconstruct with the Chinese remainder theorem.
- **Is the obstacle a huge exponent?** Verify coprimality, identify a valid group period, and reduce the exponent before powering.
- **Is the question about the power of one prime in a product, sum, factorial, or gcd?** Replace full integers with valuations and watch for equal-valuation cancellation.

**Chapter-specific stop check:** Check coprimality before modular inversion, exponent-period reduction, or the simplest CRT formula. Prime-count estimates do not certify primality.

## 3. Work the lab

Find the inverse of 17 modulo 43. Euclid gives 43=2 × 17+9, 17=9+8, and 9=8+1. Back substitution yields 1=2 × 43-5 × 17, so the inverse is -5 mod 43=38. Check 17 × 38=646=15 × 43+1. Modular division is legal because the gcd is one.

Predict the sign and scale before running the code. Then change one input and explain why the result moves. The code checks the constructed example; it does not prove the rule for every possible input. Code assertions may describe the example's chosen regime, so inspect them before changing that regime.

```python
import math
integer, modulus = 17, 43
assert modulus > 1
common_divisor = math.gcd(integer, modulus)
print("gcd:", common_divisor)
if common_divisor == 1:
    inverse = pow(integer, -1, modulus)
    print("Inverse:", inverse, "check:", integer*inverse % modulus)
    assert integer*inverse % modulus == 1
else:
    print("No multiplicative inverse exists for these inputs.")
```

**My prediction, observed result, and explanation:**

_Record your work here._

## 4. Practise without the answers

### Exercise 1

How many positive divisors does 360=2^3 × 3^2 × 5 have?

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

### Exercise 2

Solve x=2 mod 3 and x=3 mod 5.

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

### Exercise 3

Can you divide by 6 modulo 15 by finding its inverse?

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

**Coaching prompt:** “Use the Chapter 8 skill to help me with Exercise 2. Ask for my attempt, give one useful hint if I need it, and help me check the assumptions before showing the answer.”

## 5. Answer key and reasoning

Read this after attempting the exercises, or use it immediately if you prefer a complete walkthrough. An answer is complete only when its assumptions and stopping point are clear.

### Answer 1

Choose exponents independently: (3+1)(2+1)(1+1)=24 divisors.

### Answer 2

The solution is x=8 mod 15. Both congruences hold and the moduli are coprime, so this residue is unique modulo 15.

### Answer 3

No: gcd(6,15)=3. For example 6x=3 mod 15 instead reduces to 2x=1 mod 5, giving x=3 mod 5, or residues 3,8,13 modulo 15.

## 6. Build the complete chapter toolkit

The new lab samples the chapter; the following checklist covers all 10 rules. Study one thematic group at a time. A large group can take several sessions.

- **Extract Divisibility Information Efficiently:** work with rules 8.1.1, 8.1.2, 8.1.3.
- **Solve Congruences by Reducing and Reconstructing:** work with rules 8.2.1, 8.2.2, 8.2.3.
- **Match Prime and Power Structure to the Task:** work with rules 8.3.1, 8.3.2, 8.3.3, 8.3.4.

For each selected rule, read its equation, explanation, and worked use in the source. Reproduce that example; change one input; then change one assumption so the rule is no longer justified. Record the result and what check catches the failure. Historical examples remain labeled and qualified as in the source.

Read each complete numbered profile in the [chapter reference](../skills/math-thumb-number-theory/references/chapter.md) before applying it. The cues below abbreviate the graph metadata; they are not complete conditions. Change the status only after doing the practice described below.

| Rule | Book role | First assumptions to inspect | Practice status |
|---|---|---|---|
| 8.1.1: Use remainders instead of factoring to find a gcd | Independent | integer inputs not both zero | new |
| 8.1.2: Read the divisor count from prime exponents | Independent | positive integer;  complete prime factorization | new |
| 8.1.3: Estimate prime counts by n over log n | Independent | large positive bound;  natural logarithm | new |
| 8.2.1: Reduce modulo m at every arithmetic step | Workflow | common modulus;  operations respect congruence | new |
| 8.2.2: Use extended Euclid to find modular inverses | Independent | integer modulus greater than one;  coprime value and modulus for inverse | new |
| 8.2.3: Split coprime congruences with the Chinese remainder theorem | Independent | pairwise coprime moduli;  integer residues | new |
| 8.3.1: Test divisors only through the square root | Workflow | positive integer candidate;  all possible divisors through square root checked | new |
| 8.3.2: Use a sieve when you need many primes at once | Workflow | known finite upper bound;  many queries or full prime list needed | new |
| 8.3.3: Reduce modular exponents using the group period | Workflow | base coprime to modulus;  known totient or prime modulus | new |
| 8.3.4: Use p-adic valuations to track prime-power divisibility | Workflow | nonzero integer or rational input;  fixed prime | new |

For a completed row, record: **rule number / my new input / mathematical claim type / verified assumptions / calculation / check / valid use / rejected use / next step**. “Practised” means you worked an example. “Demonstrated” means you can explain a valid use, transfer it, and reject a misuse without the answer key.

## 7. Apply it to your own problem

Return to your opening question. Choose the smallest rule set that can settle it. Use the book's independent/workflow/specialized classification separately from the claim type (exact, approximate, bound, diagnostic, or heuristic).

- Selected rule number(s) and reason:
- Assumptions that hold, fail, or remain uncertain:
- Substitution with units:
- Result and error, uncertainty, or bound:
- Independent check or limiting case:
- Decision this supports:
- Stop here, do a named next calculation, or gather missing information:

## 8. Transfer and continue

Useful nearby chapters: Chapter 9: combinatorics; Chapter 10: graph theory; Chapter 21: scientific computing. Bring the question, units, assumptions, result type, and uncertainty to the next chapter. Choose a bridge only when it supplies an operation you actually need.

**Completion check:** Explain this chapter's lab in your own words; solve one changed-input exercise; reject one invalid use; and produce a decision record for your own problem. If one check fails, revisit that part of the chapter rather than marking every rule complete.