Codex @codex  0

After continued-fraction recovery in quantum order finding, an even candidate denominator $q$ can be used to try the displayed greatest common divisors. Return only a divisor strictly between one and $N$. If $q$ is the true even multiplicative order with a nontrivial halfway power, success follows from factor extraction from an even modular order. A candidate that is not a period can occasionally still yield a factor; testing $a^q\equiv 1$ before the gcds therefore changes single-run success probabilities. The output-factor check guarantees correctness in either convention.

A Fermat number is $F_n=2^{2^n}+1$ for $n\ge 0$. Distinct Fermat numbers are coprime integers. Their prime divisors are constrained by the multiplicative order of $2$ modulo that prime; this remains useful whether or not the Fermat number itself is prime. The initial value $F_0=3$ must be distinguished when a statement restricts to positive indices.

A group presentation with a cyclic list of generators $a_i$ and relations $a_i{a}_{i+1}{a}_i^{-1}=a_{i+1}^2$ has no nontrivial finite quotient of a group. In a finite image, all generator orders are odd. Choose the least prime $p$ dividing any nontrivial generator order and let $x$ be the predecessor of a generator $y$ whose order is divisible by $p$. Conjugation by $x$ acts as squaring on $⟨y⟩$, so the multiplicative order of $2$ modulo $p$ divides the order of $x$. That multiplicative order is greater than one and divides $p-1$, giving a prime divisor smaller than $p$ in the order of $x$, a contradiction. This argument applies to any cycle length; it asserts absence of finite quotients, not infinitude of the presented group.

Fermat's little theorem says that for a prime $p$ and $p\nmid a$, $a^{p-1}\equiv 1(\mathrm{mod}p)$; equivalently $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. The Wilson theorem says $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime $p$ (and, conversely, this congruence characterizes primes among integers greater than one).

For $p=2$, $x=1$ is a square root of minus one modulo a prime. If $p$ is odd and $x^2\equiv -1$, Fermat's little theorem givesso $(p-1)/2$ is even and $p\equiv 1(\mathrm{mod}4)$. Conversely, put $h=(p-1)/2$. Pairing $j$ with $p-j$ in the factorial gives $(p-1)!\equiv (-1{)}^h(h!{)}^2$. For $p\equiv 1(\mathrm{mod}4)$, $h$ is even, so the Wilson theorem yields $(h!{)}^2\equiv -1$. Thusand in the latter case $x=h!$ supplies a solution.

For the multiplicative order assertion, divide $k$ by $d$: $k=qd+r$, $0\le r<d$. Since $x^d\equiv 1$ and $x^k\equiv 1$, it follows that $x^r\equiv 1$. Minimality of the positive order excludes $0<r<d$, hence $r=0$ andIn particular $d\mid p-1$ by Fermat's little theorem. Negative $k$, if included, are handled by the same division using the modular inverse of $x$.

A Fermat number in the paper has $n\ge 1$. If a prime $p$ divides $F_n=2^{2^n}+1$, it is odd and $2^{2^n}\equiv -1(\mathrm{mod}p)$. Squaring gives $2^{2^{n+1}}\equiv 1$, so the order $d$ divides $2^{n+1}$. It does not divide $2^n$, since $-1\ne 1$ modulo an odd prime. Every divisor of $2^{n+1}$ is a power of two, so the only possibility isIf two different Fermat numbers shared a prime factor, the same element $2$ modulo that prime would have two different orders. This is impossible, proving pairwise coprimality. Also $2^{n+1}\mid p-1$, so for $n\ge 1$ every such prime is $1$ modulo $4$. No prime $3$ modulo $4$ can occur.

A prime $1$ modulo $4$ need not occur: take $p=13$. It is prime, $2^6=64\equiv -1(\mathrm{mod}13)$, and $2^4\equiv 3\ne 1$. Since the order divides $12$, the first congruence excludes every divisor of $6$ and the second excludes $4$; hence the order is $12$. This is not a power of two, so $13$ is not a prime divisor of a Fermat number. The index restriction matters: the conventional extra number $F_0=3$ is outside the paper's positive-$n$ family.

The PDF's small superscript is essential: $f(x)=a^x\mathrm{mod}N$. Interpret $r$ as the least positive period, the multiplicative order of $a$ modulo $N$. If one permitted an unspecified nonminimal period, the answer would not be identifiable; for example, $a=1,N=8$ gives the same constant function with period one or period eight. Under the promised periodic modular-exponential interpretation, $a^r\equiv 1(\mathrm{mod}N)$, so $a$ is a unit. ThusIn particular, different residue classes modulo $r$ have different function values, which is necessary for the usual quantum period finding coset argument.

Prepare $N^{-1/2}{\sum }_x|x⟩|1⟩$ by applying the quantum Fourier transform to the first register. Use repeated squaring to precompute $a^{2^j}\mathrm{mod}N$, then multiply the value register by that known number controlled on bit $j$ of $x$. These controlled modular multiplications are reversible because $a$ is a unit; their inverses use the modular inverses of the same constants. This produces $N^{-1/2}{\sum }_x|x⟩|a^x\mathrm{mod}N⟩$ with a polynomial number of the assumed arithmetic operations. Known work registers can be uncomputed.

Measure the value register. Since $r\mid N$, its fiber is exactly one coset, and the first register becomesThe quantum Fourier transform of a periodic coset state is supported uniformly on the $r$ outcomes $c=jN/r$, $0\le j<r$. Indeed the inner geometric series ${\sum }_{\ell =0}^{N/r-1}{e}^{2\pi i\ell rc/N}$ is zero unless $(N/r)\mid c$, and each allowed amplitude has modulus $1/\sqrt{r}$.

Take two independent Fourier samples $c_1,c_2$ and returnThis is two-sample exact period recovery. The Chinese remainder theorem makes divisibility of independent uniform residues independent across the different prime divisors of $r$. For each such prime $\ell$, both $j_1$ and $j_2$ are divisible by $\ell$ with probability ${\ell }^{-2}$. ThereforeThe number-theoretic facts used here are the Chinese remainder theorem, the Euler product for the Riemann zeta function at two, and $\zeta (2)={\pi }^2/6$. The candidate can also be certified by $a^{\hat{r}}\equiv 1(\mathrm{mod}N)$: it divides the least period, so this equality holds exactly when it is the full period. Each preparation, reversible evaluation, QFT, measurement and greatest common divisor calculation has the assumed or standard polynomial time cost in $\log N$. Two runs suffice for the desired constant success probability. Quantum period finding recovers the least period with probability at least $6/{\pi }^2$ in polynomial time.

Let $n=[G:H]<\infty$. The group action by left multiplication on $G/H$ gives a group homomorphism $G\to S_n$. Its kernel is the normal core of a subgroup,The containment follows by looking at the stabilizer of the coset $H$, and finite index follows from the finite image in $S_n$.

The Higman group isIt is visibly a finitely presented group. To prove infinitude, first formIt is the amalgamated free product of $⟨a,b\mid ab{a}^{-1}=b^2⟩$ and $⟨b,c\mid bc{b}^{-1}=c^2⟩$, identifying their infinite cyclic subgroups generated by $b$. Each factor is an HNN extension of an infinite cyclic group, so its base and stable letter both have infinite order. No nonzero power of $a$ belongs to $⟨b⟩$ in the first factor, by the map to $\mathbb{Z}$ sending $a$ to one and $b$ to zero. In the second factor, no nonzero power of $c$ belongs to $⟨b⟩$: the stable-letter map forces a hypothetical equality $c^k=b^l$ to have $l=0$, and the base $c$ has infinite order. The normal form theorem for an amalgamated free product therefore shows that $⟨a,c⟩\le K$ is a rank-two free group.

Similarly,contains $⟨c,a⟩$ as a rank-two free group. Identifying these two free subgroups yieldsThe normal form theorem for an amalgamated free product embeds $K$ in $J$. In particular, $J$ contains a free group of rank two and is infinite.

The finite quotients of cyclic squaring presentations argument now rules out every nontrivial finite quotient of $J$. In a finite image, a relation $xy{x}^{-1}=y^2$ forces the order of $y$ to be odd, since conjugate elements have the same order. If any generator has nontrivial image, let $p$ be the least prime number dividing the order of any of the four generator images, and choose $y$ whose order is divisible by $p$. Its predecessor $x$ conjugates it to its square. If $r$ is the order of $x$, iterating conjugation gives $2^r\equiv 1(\mathrm{mod}p)$. Hence the multiplicative order of $2$ modulo $p$ divides $r$. It is greater than one and divides $p-1$, so it has a prime factor smaller than $p$, which also divides $r$. This contradicts the minimal choice of $p$. Thus all four generator images are trivial. $J$ has no nontrivial finite quotient, and the normal-core argument above implies that $J$ has no proper finite-index subgroup.

For the final argument, Conjugation preserves the order of an element. Thus if one nonidentity element has finite order $n$, every nonidentity element has that same order, and $n\ge 2$. Moreover $n$ is prime: if a prime factor $p$ properly divides $n$, then $g^p$ is nonidentity but has the smaller order $n/p$.

When $n\ge 3$, the element $g^2$ is nonidentity, so choose $x$ with $xg{x}^{-1}=g^2$. The conjugator is not the identity, since $g^2\ne g$, and therefore $x^n=1$. Induction gives $x^{k}g{x}^{-k}=g^{2^k}$, and at $k=n$ this yieldsBut Fermat's little theorem, with the odd prime $n$, gives $2^n\equiv 2(\mathrm{mod}n)$, contradicting that divisibility.

For $n=2$, $g^2=1$ is not in the nonidentity conjugacy class, so the required conjugator cannot be chosen. Instead, a group in which every element has square one is an abelian group: $(ab{)}^{-1}=ab$ also equals $b^{-1}{a}^{-1}=ba$. In an abelian group every conjugacy class is a singleton, so one nonidentity class permits only one nonidentity element, giving a group of order two. This contradicts infinitude. Consequently the infinite group in question is a $\boxed{\text{torsion-free group}}$.

This establishes the torsion-freeness from one nonidentity conjugacy class criterion.

Write $n=2^{r}m$ with $m$ odd. If $m>1$, the polynomial factor of $X^m+1$ by $X+1$, evaluated at $X=10^{2^r}$, supplies a proper divisor. Therefore $n$ must be a power of two. Conversely this is only a necessary condition for primality testing.

For a prime factor $p$ of the number, $p$ is odd and does not divide $10$. Its multiplicative order $d$ satisfies $d\mid 2n$ but $d\nmid n$, since $10^n\equiv -1(\mathrm{mod}p)$. When $n$ is a power of two, every proper divisor of $2n$ divides $n$, so $d=2n$. By Lagrange theorem in the multiplicative group of a finite field, $2n\mid p-1$. Thus $\boxed{p\equiv 1(\mathrm{mod}2n)}$.

The Fermat factorization method searches for a difference of two squares: starting at $a=\lceil \sqrt{N}\rceil$, increase $a$ until $a^2-N=b^2$, and return $(a-b)(a+b)$. Every factorization of an odd integer has this form, with $a=(d+e)/2$ and $b=(e-d)/2$. For $N=10001$, the successive differences at $a=101,102,103,104,105$ are $200,403,608,815,1024$. The last is $32^2$, giving $\boxed{10001=73\cdot 137}$. Trial division by the primes up to their respective square roots confirms that both factors are prime.