Manuscript Oai279-A@1 · Oai279-A.tex · lemma · a1abc73f

Lemma: Order candidates and a uniform arithmetic lower bound

Stage 1: audit the five interfaces without importing them › Interface 2: the prescribed order trial · lines 431–472 · proof included or linked

Oai279-A@1#lem:order-arithmetic

Back to manuscript

If $a$ is a unit modulo $m$ , then

a^{d} \equiv 1 (mod m) ⟺ r ∣ d .

For $1 \leq r < 2^{n}$ , the right-hand side of (eq:order-law) satisfies

0 < φ (r) λ (r) \leq \frac{1}{1024}, φ (r) λ (r) \geq \frac{1}{2048 ( n + 1 )} .

These are arithmetic statements about the proposed law, not a construction of a trial realizing it.

Proof. Divide $d = q r + s$ , with $0 \leq s < r$ . If $a^{d} = 1$ , then $a^{s} = 1$ , so minimality of $r$ forces $s = 0$ . The converse is immediate.

Let $p_{1} < \dots < p_{k}$ be the distinct prime divisors of $r > 1$ . Since $p_{i} \geq i + 1$ ,

\frac{φ ( r )}{r} = i = 1 \prod^{k} (1 - \frac{1}{p _{i}}) \geq i = 1 \prod^{k} \frac{i}{i + 1} = \frac{1}{k + 1} \geq \frac{1}{n + 1} .

The case $r = 1$ uses $φ (1) = 1$ . Also

\frac{1}{2048 r} \leq λ (r) \leq \frac{1}{1024 r}, φ (r) \leq r .

Multiplying gives the assertions.

Displayed formulas in this passage

unlabeled · line 434
$a^{d} \equiv 1 (mod m) ⟺ r ∣ d .$
unlabeled · line 439
$0 < φ (r) λ (r) \leq \frac{1}{1024}, φ (r) λ (r) \geq \frac{1}{2048 ( n + 1 )} .$
unlabeled · line 455
$\frac{φ ( r )}{r} = i = 1 \prod^{k} (1 - \frac{1}{p _{i}}) \geq i = 1 \prod^{k} \frac{i}{i + 1} = \frac{1}{k + 1} \geq \frac{1}{n + 1} .$
unlabeled · line 467
$\frac{1}{2048 r} \leq λ (r) \leq \frac{1}{1024 r}, φ (r) \leq r .$

Lemma: Order candidates and a uniform arithmetic lower bound

Displayed formulas in this passage

Nearby in this section