E128: Quadratic modular obstructions (Euler-type)¶
Tags: number-theory, model-checking, counterexample-search, primes
See: Valid Tags.
Highlights¶
Makes the “hidden reason” a prime streak must fail: modular obstructions.
Lists explicit residue classes \(n\bmod p\) that force divisibility of \(f(n)\).
Includes the classic witness \(n=41k\) for Euler’s \(n^2+n+41\).
Goal¶
Show how congruences explain why a “prime-generating polynomial” cannot stay prime forever. For each small prime modulus \(p\), we compute the roots of \(f(n)\equiv 0\pmod p\).
Background (quick refresher)¶
Research question¶
For Euler’s \(f(n)=n^2+n+41\), which small primes \(p\) divide some values \(f(n)\), and which residue classes \(n\bmod p\) generate those guaranteed composites?
Method¶
Fix \(f(n)=n^2+an+b\) with \((a,b)=(1,41)\).
For each prime \(p\le p_{\max}\), brute-force all residues \(n\in\{0,\dots,p-1\}\) and record solutions to \(f(n)\equiv 0\pmod p\).
Plot the number of roots per prime and write a report table of residues.
How to run¶
make run EXP=e128
or:
uv run python -m mathxlab.experiments.e128
Outputs¶
This experiment follows the standard output contract:
out/e128/figures/— generated figures (PNG)out/e128/report.md— short narrative reportout/e128/params.json— run parameters (stable JSON)out/e128/logs/— run logs (created by the runner/Makefile)
Published run snapshot¶
If this experiment is included in the docs gallery, include the published snapshot (report + params).
Reproduce:
make run EXP=e128
Parameters¶
a:
1b:
41p_max:
199max_listed:
25witness_k:
6
Key observation¶
For any modulus p, the congruence f(n)≡0 (mod p) selects residue classes. Whenever n hits such a class, f(n) is divisible by p and therefore composite (unless f(n)=p).
A built-in infinite composite subsequence (Euler-style)¶
For f(n)=n^2+an+b and n=bk:
k |
n=bk |
f(n) |
divisible by |
|---|---|---|---|
1 |
41 |
1763 |
41 |
2 |
82 |
6847 |
41 |
3 |
123 |
15293 |
41 |
4 |
164 |
27101 |
41 |
5 |
205 |
42271 |
41 |
6 |
246 |
60803 |
41 |
Roots modulo small primes¶
The table below lists primes p for which f(n)≡0 (mod p) has solutions.
p |
root count |
roots n (mod p) |
|---|---|---|
41 |
2 |
0, 40 |
43 |
2 |
1, 41 |
47 |
2 |
2, 44 |
53 |
2 |
3, 49 |
61 |
2 |
4, 56 |
71 |
2 |
5, 65 |
83 |
2 |
6, 76 |
97 |
2 |
7, 89 |
113 |
2 |
8, 104 |
131 |
2 |
9, 121 |
151 |
2 |
10, 140 |
163 |
1 |
81 |
167 |
2 |
82, 84 |
173 |
2 |
11, 161 |
179 |
2 |
87, 91 |
197 |
2 |
12, 184 |
199 |
2 |
96, 102 |
Outputs¶
figures/fig_01_root_counts_mod_p.pngparams.jsonreport.md
params.json (snapshot)
{
"a": 1,
"b": 41,
"max_listed": 25,
"p_max": 199,
"seed": 1,
"witness_k": 6
}