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.

For an integer $n>1$, the Carmichael function $\lambda (n)$ is the exponent of a finite group for the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$: the least positive integer $m$ for whichHere the greatest common divisor condition selects the units. Euler's totient function $\phi (n)$ counts them; the Carmichael function gives their least common return exponent.^[ref]

Modulo eight, the units are $1,3,5,7$, and their squares are all congruent to one. Their multiplicative orders are $1,2,2,2$, so $\lambda (8)=2$ although $\phi (8)=4$. Modulo fifteen, the units $1,2,4,7,8,11,13,14$ have multiplicative orders $1,4,2,4,4,2,4,2$. For example, the powers of two return through $1,2,4,8,1$. Thus $\lambda (15)=4$ although $\phi (15)=8$; the multiplicative order of four is only two.

The three quantities are related byA common return exponent must be a multiple of every multiplicative order, hence of their least common multiple. Conversely, that least common multiple makes every unit return to one. Lagrange's theorem makes each multiplicative order divide the group order $\phi (n)$, proving the final divisibility. The Carmichael function applies to all units at once, while the multiplicative order concerns a chosen unit.

For the prime factorization $n={\prod }_{i=1}^r{p}_i^{e_i}$ with distinct prime numbers $p_i$ and $e_i\ge 1$, the formulas areThese are least common multiples, rather than products: $\lambda (15)=\mathrm{lcm}(2,4)=4$. The convention $\lambda (1)=1$ handles the trivial case separately.^[ref]

The Chinese remainder theorem for unit groups explains the least common multiple: a power returns to one in every prime power component exactly when it is a multiple of each component's exponent of a finite group. For an odd prime power, the unit group is a cyclic group of group order $p^{e-1}(p-1)$. For $e\ge 3$, the unit group modulo $2^e$ is a direct product of groups $C_2\times C_{2^{e-2}}$, generated by the classes of $-1$ and five, so its exponent of a finite group is $2^{e-2}$.^[ref]

This gives a uniform reduction for modular exponentiation: for a unit $a$ and a nonnegative integer $k$, reduce $k$ modulo $\lambda (n)$. For example, $2^{1001}\equiv 2(\mathrm{mod}15)$ because $1001\equiv 1(\mathrm{mod}4)$. The unit hypothesis matters: $3^2\equiv 1(\mathrm{mod}8)$, but $2^2\not\equiv 1(\mathrm{mod}8)$. Computing the formula assumes the prime factorization is available. The same common-exponent viewpoint explains Carmichael numbers: a composite number $n$ passes the Fermat primality test for every unit base exactly when $\lambda (n)\mid n-1$. For example, $\lambda (561)=\mathrm{lcm}(2,10,16)=80\mid 560$.

For a reduced fraction $p/q$ with $0<p<q$, $q>1$, and $q,10$ coprime integers, its decimal representation repeats immediately after the decimal point. The shortest repeating block has lengthHere $\mathrm{ord}$ denotes multiplicative order, and $\phi$ denotes Euler's totient function. Changing the numerator preserves the decimal period as long as the fraction remains reduced.^[ref]

For example, long division of $1/7$ gives the remainders $1,3,2,6,4,5,1$, with emitted digits $1,4,2,8,5,7$. ConsequentlyEach remainder determines both the next digit and the next remainder; returning to one restarts the same six steps.

More generally, initialize long division with $r_0=p$. At each step, division with remainder givesso $r_j\equiv p10^j(\mathrm{mod}q)$. Since $p,q$ are coprime integers, the modular inverse of $p$ shows that $r_L=r_0$ exactly when $10^L\equiv 1(\mathrm{mod}q)$. To see why the digit block cannot repeat sooner than the remainders, a purely repeating decimal with a block of $L$ digits represents $D/(10^L-1)$ for an integer $D$. A reduced fraction $p/q$ with that value forces $q\mid 10^L-1$. Hence the shortest digit repeat and the multiplicative order coincide.

Knowing the decimal period predicts how many digits must be computed and stored: one block determines the whole repeating decimal. It also constructs the block directly. With $L={\mathrm{ord}}_q(10)$, the integeris the block, padded on the left with zeros to $L$ digits. For $1/11$, $L=2$ and $D=9$, so the block is $09$ and $1/11=0.\overline{09}$. Reduction matters: $7/21=1/3=0.\overline{3}$ has decimal period one, whereas ${\mathrm{ord}}_{21}(10)=6$.

If the reduced denominator contains prime factors two or five, ten has no multiplicative order modulo that whole denominator. WriteThe decimal preperiod has exactly $k_0$ digits. If $m>1$, the remaining repeating decimal has decimal period ${\mathrm{ord}}_m(10)$. For instance, $28=2^2\cdot 7$ gives $1/28=0.03\overline{571428}$: two prefix digits, then six repeating digits. If $m=1$, the decimal representation is a terminating decimal with exactly $k_0$ fractional places. We use the representation ending in zeros, rather than its alternative ending in nines; for example $1/40=0.025$ terminates after three places.

A short derivation explains both cases. After $k$ digits, multiplying the reduced fraction by $10^k$ and discarding its integer part leaves a reduced fraction whose denominator is $q/\gcd (q,10^k)$. This denominator first becomes coprime to ten at $k=k_0$. It then equals $m$, giving an immediate repeat when $m>1$, or an integer when $m=1$. The same long division argument works for positional notation in any base $b\ge 2$: for a reduced denominator $q>1$ coprime to $b$, the shortest repeating block has length ${\mathrm{ord}}_q(b)$.

For an integer modulus $n\ge 2$ and an integer $a$ with greatest common divisor $\gcd (a,n)=1$, Euler's theorem, also called the Fermat-Euler theorem, statesHere Euler's totient function $\phi (n)$ counts the units in the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$. These congruence classes have modular multiplicative inverses, equivalently their representatives are coprime to $n$. The guaranteed return to one permits exponent reduction for units.^[ref]

For a prime number $p$, $\phi (p)=p-1$, recovering Fermat's little theorem in the form $a^{p-1}\equiv 1(\mathrm{mod}p)$ when $p\nmid a$. Multiplying by $a$ and separately handling $p\mid a$ gives $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. For a composite number used as the integer modulus, a nonzero congruence class can be a nonunit.

Modulo twelve, the units have representatives $1,5,7,11$, so Euler's totient function gives $\phi (12)=4$. Multiplication by five producesThus this permutation has two permutation cycles, each of length two. In particular $5^2\equiv 1(\mathrm{mod}12)$, and the guaranteed return $5^4\equiv 1$ follows. The number of units need not be the length of one permutation cycle. Modulo fifteen, multiplication by seven similarly gives the two permutation cycles $(1,7,4,13)$ and $(2,14,8,11)$, covering all eight units. The powers of seven follow the permutation cycle containing one; the other permutation cycle shows that these powers do not visit every unit.

There is a stronger obstruction for a nonunit than just an occasional failed calculation. If a positive integer $d>1$ divides both $a$ and $n$, then $a^k\equiv 0(\mathrm{mod}d)$ for every $k\ge 1$, so $a^k$ cannot be congruent to one modulo $n$. For example, $\gcd (3,15)=3$ and $3^{\phi (15)}=3^8\equiv 6(\mathrm{mod}15)$, rather than one. Such a base has no multiplicative order modulo that integer modulus.^[ref]

For a unit modulo n $a$ and a nonnegative integer $k$, division with remainder writes $k=q\phi (n)+r$ with $0\le r<\phi (n)$. Euler's theorem then givesThis replaces a potentially enormous exponent by a small remainder. The exponent itself is reduced modulo Euler's totient function, while the powers are reduced modulo $n$: these are different integer moduli.

For a worked modulo-fifteen calculation, seven is coprime to fifteen and $\phi (15)=8$. ThereforeUse exponentiation by squaring on the remaining exponent $5=(101{)}_2$, reducing after each multiplication:Thus $7^{2029}\mathrm{mod}15=7$. Modular exponentiation supplies the computation; Euler's theorem supplies the optional shortening of its exponent. Exponentiation by squaring also works for nonunit bases, without using this shortening.

The guaranteed exponent $\phi (n)$ is a common return exponent and an upper bound on the shortest period; it need not be that period. The multiplicative order $d={\mathrm{ord}}_n(a)$ is the least positive return exponent for the chosen unit. The Carmichael function $\lambda (n)$ is the least positive return exponent that works for every unit. Their precise relation isEither smaller return exponent can replace $\phi (n)$ in exponent reduction for units. Modulo fifteen, ${\mathrm{ord}}_{15}(7)=\lambda (15)=4<8=\phi (15)$, so $2029=507\cdot 4+1$ gives $7^{2029}\equiv 7$ immediately. For base four the multiplicative order is only two, smaller even than $\lambda (15)$. A return at exponent eight alone does not prove that the multiplicative order is eight.^[ref]

If the reduced exponent is zero, the rule gives $a^k\equiv a^0=1$, and still requires a unit. Applying it to the nonunit three would falsely predict $3^8\equiv 3^0=1(\mathrm{mod}15)$; the actual residue is six. For negative exponents, first interpret the power using a modular multiplicative inverse, as in modular exponentiation.

For a prime number $p$ and an integer $a$ not divisible by $p$, Fermat's little theorem states the modular congruenceEquivalently, for every integer $a$, including $a<0$ and multiples of $p$,The first formulation follows from the second by multiplying by a modular multiplicative inverse of $a$. Conversely, multiply the first by $a$ when $p\nmid a$; when $p\mid a$, both sides of the second are zero modulo $p$. The divisibility condition in the first formulation is essential.^[ref]

For $p=7$, $3^6=729=7\cdot 104+1$, so $3^6\equiv 1(\mathrm{mod}7)$ and $3^7\equiv 3(\mathrm{mod}7)$. Also $(-2{)}^6=64\equiv 1(\mathrm{mod}7)$, while $7^6\equiv 0(\mathrm{mod}7)$: a zero residue class cannot satisfy the first formulation. It does satisfy $7^7\equiv 7\equiv 0(\mathrm{mod}7)$. A failure at a zero residue class therefore says nothing against a candidate's being a prime number.

The prime number $p=2$ is included. Its only nonzero residue class is one: every odd integer $a$ satisfies $a^{2-1}=a\equiv 1(\mathrm{mod}2)$. Every integer also satisfies $a^2\equiv a(\mathrm{mod}2)$, because $a(a-1)$ is even. Testing the first formulation with an even integer would violate its hypothesis.

The useful surprise is that every nonzero residue class returns to one at the same exponent $p-1$, although its shortest return can be earlier. This gives exponent reduction for units: for a nonnegative integer $k$, $a^k\equiv a^{k\mathrm{mod}(p-1)}(\mathrm{mod}p)$ when $p\nmid a$. It also computes a modular multiplicative inverse as $a^{p-2}$ modulo $p$, including $p=2$. Repeated squaring makes these modular exponentiations practical.

In group theory, the nonzero residue classes form the multiplicative group of integers modulo n with $n=p$, of group order $p-1$. Lagrange's theorem says that the multiplicative order of $a$ divides $p-1$, giving the guaranteed return. Euler's theorem extends this to a general integer modulus $n$, using the units and Euler's totient function $\phi (n)$; the Carmichael function gives the least common return exponent for all units. A nonzero residue class modulo a composite number need not be a unit.

Leonhard Euler's paper presented in 1732 and published in 1738 states a historical formulation: Theorem 1 says that powers with exponent $n-1$ leave zero or one upon division by a prime number $n$. The preceding discussion states the difference-of-powers version and explicitly says that he does not have its proof.^[ref]

A Fermat number is the positive integer $F_n=2^{2^n}+1$, indexed by a nonnegative integer $n$. The first five are $3,5,17,257,65537$, all prime numbers; the next is the composite number $F_5=4294967297=641\cdot 6700417$. This family offers a compact lesson in number theory: a very persuasive finite pattern can fail, while an exact divisibility relation settles a gigantic case with little computation.

Why does the exponent itself have the form $2^n$? Suppose $m=ab$ is a positive integer with an odd integer factor $b>1$. The polynomial factorization $x^b+1=(x+1)(x^{b-1}-x^{b-2}+\cdots -x+1)$ shows that $2^a+1$ is a proper divisor of $2^m+1$. Consequently, if $2^m+1$ is a prime number, $m$ must be a power of two. That is a necessary condition, rather than a promise that the surviving candidates are prime.

The Fermat number product identity makes distinct Fermat numbers coprime integers. Thus every term has a prime factor absent from all earlier terms, whether or not that term is itself a prime number. This gives an explicit route to infinitely many different prime numbers, without establishing that infinitely many terms of this particular sequence are prime. Meanwhile the prime divisor of a Fermat number criterion filters possible factors through a small multiplicative order calculation.

The family also links arithmetic to Euclidean geometry: a constructible regular polygon can have a number of sides equal to a power of two times a product of distinct Fermat primes. The Gauss-Wantzel theorem gives the precise criterion. For instance, $15=3\cdot 5$ and $17$ qualify, but $9=3^2$ does not. The word "distinct" matters. Carl Pomerance describes this connection in Primality testing: then and now by Carl Pomerance (slide 18).

Historically, Leonhard Euler records Pierre de Fermat's proposed primality pattern, then refutes it by finding the factor $641$ of $F_5$. His paper was presented in 1732 and published in 1738; those are different events, not competing dates for one publication.^[ref]

A short modern check needs only two representations of $641$:In modular arithmetic these give $5^4{2}^{28}\equiv 1$ and $5^4\equiv -2^4(\mathrm{mod}641)$. Substitution yields $2^{32}\equiv -1(\mathrm{mod}641)$, so $641\mid F_5$. This verifies the factor directly; it does not claim to reconstruct Euler's search process.

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.

For coprime integers $a,n$ with $n>1$, the multiplicative order is the least positive integer $d$ such thatIt counts the distinct powers in the cyclic subgroup generated by the congruence class of $a$. Thus it is an order of a group element in the unit group $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$.^[ref]

For example, the modular exponentiation $2^k\mathrm{mod}7$, starting at $k=0$, produces $1,2,4,1,2,4,\dots$. The first return to one takes three steps, so ${\mathrm{ord}}_7(2)=3$. Starting at the congruence class three and repeatedly multiplying by two instead gives $3,6,5,3,\dots$: these are the other three units modulo seven, outside the cyclic subgroup generated by two.

Euler's theorem guarantees a return to one at exponent $\phi (n)$, where $\phi$ is Euler's totient function. Thus the multiplicative order exists for every unit.^[ref] In fact,By Lagrange's theorem, the size of the cyclic subgroup divides the size of the unit group, which is Euler's totient function. For two modulo seven, this is $3\mid 6$; the multiplicative order need not equal Euler's totient function. If $a\equiv 1(\mathrm{mod}n)$, its multiplicative order is one.

The coprime integers hypothesis is necessary: if $a^d=1+kn$, any common divisor of $a$ and $n$ divides one. For instance, powers of two modulo eight give $1,2,4,0,0,\dots$, with no positive-exponent return to one. This sequence eventually settles, but two has no multiplicative order modulo eight.

For a prime number $p$ and $p\nmid a$, multiplication by $a$ gives a permutation of the $p-1$ nonzero residue classes. For $a=3$ modulo seven, the representatives $1,2,3,4,5,6$ map to $3,6,2,5,1,4$: the same collection in a different order. Repeating this permutation from one visits all six representatives before returning.

For $a=2$ modulo seven, the permutation cycles are instead $(1,2,4)$ and $(3,6,5)$. The powers of two visit only the permutation cycle containing one, so their multiplicative order is three. Both permutation cycles return after three steps; applying the permutation six times still fixes every nonzero residue class. Fermat's little theorem guarantees a return at six, not that every base visits every nonzero residue class.

More generally, every permutation cycle of this map has length equal to the multiplicative order of $a$: starting at a nonzero residue class $x$, a return means $a^{k}x\equiv x(\mathrm{mod}p)$, and its modular multiplicative inverse allows cancellation of $x$. Thus the $p-1$ nonzero residue classes split into equal-length permutation cycles, which also explains the divisibility of the multiplicative order into $p-1$.

The product argument gives a short proof outline. Since multiplication by $a$ is a permutation of the nonzero residue classes,Every factor is a unit, so their product has a modular multiplicative inverse and can be cancelled. This leaves $a^{p-1}\equiv 1(\mathrm{mod}p)$. The whole argument works for $p=2$, where the product is just one.^[ref]

Let $a,n$ be coprime integers with $n>1$, and let $d={\mathrm{ord}}_n(a)$ be their multiplicative order. For integers $x,y$,Negative exponents mean powers of the modular inverse of $a$. Thus periodic modular exponentiation has smallest positive period $d$, and $1,a,\dots ,a^{d-1}$ are distinct congruence classes.^[ref]

This lets a huge modular exponentiation reuse a short list: reduce its exponent modulo the multiplicative order, then look up the corresponding power. For example, $1000\equiv 1(\mathrm{mod}3)$ gives $2^{1000}\equiv 2(\mathrm{mod}7)$, while $1001\equiv 2(\mathrm{mod}3)$ gives $2^{1001}\equiv 4(\mathrm{mod}7)$. When the multiplicative order is unknown, Euler's theorem permits reduction modulo Euler's totient function, though that period may be longer. Repeated squaring remains useful when computing either the unreduced or the reduced power.

For a proof outline, multiply $a^x\equiv a^y$ by the modular inverse of $a^y$, leaving $a^{x-y}\equiv 1$. Apply Euclidean division to write $x-y=td+r$ with $0\le r<d$. Then $a^{x-y}\equiv a^r$; minimality of the multiplicative order forces $r=0$. The reverse implication follows from $a^d\equiv 1$. The coprime integers hypothesis enables cancellation: modulo eight, $2^3\equiv 2^4\equiv 0$, but this repetition supplies no multiplicative order for two.

The fact that a nontrivial factor usually appears before a full return does not say that either event appears soon. Each iteration of the RSA cycling attack is inexpensive, but the number of iterations can be enormous. The multiplicative orders governing returns modulo $p$ and $q$ need not be small, and writing down a large return exponent does not provide a fast way to search the preceding iterations.

If this procedure factored arbitrary well-generated RSA cryptosystem moduli in feasible time with substantial success, it would solve the associated integer factorization problem efficiently. If it instead rapidly returned the predecessor of a ciphertext without factoring, it would solve the RSA inversion problem. Both are intended to be infeasible for appropriate parameters. Efficient integer factorization certainly breaks RSA cryptosystem security; the reverse implication for general RSA inversion problem algorithms is not known.

Thus the stated observation alone provides no serious general attack on well-generated parameters. It also does not prove a lower bound: special moduli or messages with short cycles can be weak, and the hardness claims are computational assumptions.

Let $d$ be the multiplicative order of $a$ modulo $p$. Use Euclidean division to write $x=qd+r$, $0\le r<d$. Since $a^d\equiv 1$,If $a^x\equiv 1$, minimality of $d$ forces $r=0$, so $d$ divides $x$. Conversely, $d\mid x$ immediately gives $a^x\equiv 1$. For negative integers $x$, powers are interpreted using the multiplicative inverse and the same argument applies.

Apply the result to $x=p-1$, using Fermat's little theorem. Then $d\mid p-1$, equivalently

If $x^2\equiv -1(\mathrm{mod}p)$ with $p$ an odd prime, then $x^4\equiv 1$ but $x^2\not\equiv 1$. The multiplicative order consequently divides four and is neither one nor two, so it is four. The preceding divisibility result makes $4\mid p-1$ necessary.

For sufficiency, suppose $p\equiv 1(\mathrm{mod}4)$ and put $r=(p-1)/2$, an even integer. Pair opposite factors in the factorial:Wilson's theorem gives $(r!{)}^2\equiv -1(\mathrm{mod}p)$, explicitly producing a square root of minus one modulo a prime. Thus

For $b>1$, Euler's theorem allows $d=\phi (b)>0$, since $a,b$ are coprime integers. At $b=1$ every congruence holds and one may take $d=1$. Let $y$ be the multiplicative order of $a$ modulo $b$. Write a nonnegative exponent $x=qy+r$ with $0\le r<y$ using the Euclidean division. Then $a^x\equiv a^r(\mathrm{mod}b)$, so $a^x\equiv 1$ implies $r=0$ by minimality of $y$. Thus $y\mid x$. Negative exponents, if included, give the same conclusion using the inverse residue of $a$.

A prime divisor of a Fermat number $F_n=2^{2^n}+1$ is odd, and satisfies $2^{2^n}\equiv -1(\mathrm{mod}p)$. Therefore $2^{2^{n+1}}\equiv 1(\mathrm{mod}p)$, so its multiplicative order divides $2^{n+1}$. It does not divide $2^n$, since $-1\ne 1$ modulo the odd prime. Every divisor of $2^{n+1}$ is a power of two, henceBy Fermat's little theorem and the divisibility just proved, $2^{n+1}\mid p-1$, giving $\boxed{p\equiv 1(\mathrm{mod}{2}^{n+1})}$.

Let $U$ be a unitary operator and suppose initially that the target is an eigenstate $|u⟩$ with $U|u⟩=e^{2\pi i\varphi }|u⟩$, $0\le \varphi <1$. Use $t$ control qubits, so $L=2^t$. Hadamard gates prepare the uniform superposition $L^{-1/2}{\sum }_{a=0}^{L-1}|a⟩$. For each binary control position $j$, apply the controlled unitary gate $U^{2^j}$. The resulting state isApply the inverse quantum Fourier transform, with convention ${\mathrm{QFT}}_L|j⟩=L^{-1/2}{\sum }_a{e}^{2\pi iaj/L}|a⟩$, and measure the control. The exact amplitude and probability areFor an exactly representable phase $\varphi =j_0/L$, orthogonality of roots of unity makes the outcome $j_0$ certain. Otherwise the finite geometric series givesThe estimate is $j/L$, with phases interpreted modulo one.

To prove an error bound, choose a nearest label $j_0$ to $L\varphi$ on the circular grid and put $d=L\varphi -j_0$ in the interval $[-1/2,1/2]$. For $d\ne 0$, concavity of sine on $[0,\pi /2]$ gives $|\sin \pi d|\ge 2|d|$, while $L|\sin (\pi d/L)|\le \pi |d|$. Therefore the nearest-integer success bound for quantum phase estimation isHere $\Vert x{\Vert }_{\mathbb{R}/\mathbb{Z}}={\min }_{k\in \mathbb{Z}}|x-k|$. At an exact grid point the probability is one. If two nearest labels tie, either one separately has the displayed lower bound.

For high confidence one can prove a stronger quantum phase estimation tail bound. Let $d_j$ be the centered distance between $j$ and $L\varphi$, chosen with $|d_j|\le L/2$. The denominator estimate $|\sin (\pi d_j/L)|\ge 2|d_j|/L$ implies $p_j\le 1/(4d_j^2)$ away from the exact-phase case. A label at circular integer distance $\ell$ from $j_0$ has $|d_j|\ge \ell -1/2$, and there are at most two labels at each such distance. For $m\ge 2$, summing the tails givesOn the complementary event the circular phase error is at most $(m-1/2)/L$. Thus, for $b$ desired bits of accuracy, take $t=b+u$ with $u\ge 1$ and $m=2^u$ to obtainTaking $u=\lceil {\log }_2(1+1/(2\epsilon ))\rceil$ makes the right side at most $\epsilon$. This adds only $O(\log (1/\epsilon ))$ control qubits. Efficient QFT is not by itself a guarantee of efficient controlled powers of an arbitrary $U$: implementing them by repeated oracle calls uses $L-1$ calls. The modular-arithmetic application has efficient powers, as follows.

Assume $n>1$ and $\gcd (x,n)=1$, and let $r$ be the multiplicative order of $x$ modulo $n$. Define the unitary operator $U_x|y⟩=|xy\mathrm{mod}n⟩$ on $0\le y<n$, and extend it as the identity on unused computational-basis labels of the binary register. Coprimality makes multiplication a permutation, so this extension really is unitary. The orbit of $|1⟩$ consists of the $r$ distinct states $|x^j\mathrm{mod}n⟩$. Its modular multiplication eigenstates areThe last relation follows by shifting the index $j$ cyclically; orthogonality follows from the finite Fourier sum. We do not need to know $r$ to prepare one of these eigenstates: the readily prepared target obeysRunning quantum phase estimation on this state produces the mixture of the $r$ eigenphase distributions, each with weight $1/r$, because the target eigenstates are orthogonal. Thus it samples a uniformly random phase label $s$ and estimates $s/r$ with the bounds just proved. Equivalently the state before the inverse QFT is $L^{-1/2}{\sum }_a|a⟩|x^a\mathrm{mod}n⟩$, which is obtained by quantum modular exponentiation directly.

The controlled power $U_x^{2^j}$ multiplies by $x^{2^j}\mathrm{mod}n$, whose constant is computed by repeated squaring. Under the assumed efficient modular exponentiation, these controlled multiplications and the QFT use a number of gates polynomial in the register lengths. Taking $L>n^2$ requires only $O(\log n)$ phase qubits. The nearest-label event has probability at least $4/{\pi }^2$ and yields an estimate within $1/(2L)<1/(2r^2)$ of $s/r$. Since $r<n$, continued-fraction recovery in quantum order finding then identifies the reduced fraction $s/r$. The denominator is $r/\gcd (s,r)$, not necessarily $r$: when $s$ and $r$ are coprime it is the desired order, and when they are not it is only a divisor. One may test candidate denominators using modular exponentiation and repeat with fresh samples; denominators from successful samples can also be combined by a least common multiple. The probability of a nearest-label sample with $s$ coprime to $r$ is at least $(4/{\pi }^2)\phi (r)/r$. These qualifications explain exactly what the phase estimate yields without falsely assuming that the unknown order or an eigenstate was available at the start.

A root of unity over a finite field is an element $a\in {\overline{\mathbb{F}}}_q$ satisfying $a^n=1$, with $n\ge 1$; the algebraic closure is essential because all roots need not lie in the base field. Write $p=\mathrm{char}{\mathbb{F}}_q$ and $n=p^{a}m$, where $p\nmid m$. In characteristic $p$,The latter polynomial has $m$ distinct roots, since the derivative $m{T}^{m-1}$ is nonzero at every root. Those roots are closed under multiplication and inversion and contain $1$, so $E(n,q)$ is a finite multiplicative subgroup of a field. The proof in the preceding solution makes it a cyclic group. In particularThis also explains why the coprimality qualification is needed.

The multiplicative group of a finite field ${\mathbb{F}}_{q^s}^{\times }$ is cyclic of order $q^s-1$. It contains the entire group of $m$th roots precisely when $m\mid q^s-1$. For necessity, a generator of $E(n,q)$ has order $m$ and Lagrange's theorem applies. For sufficiency, a cyclic group whose order is divisible by $m$ contains $m$ roots of $T^m-1$; since there are exactly $m$ roots in the algebraic closure, these are all of them. Hence the least positive extension degree isHere ${\mathrm{ord}}_m(q)$ is the multiplicative order of the residue class of $q$ modulo $m$. If $n$ is coprime to $q$, replace $m$ by $n$. Existence of this order follows because $q$ is a unit modulo $m$.

A primitive $n$th root of unity over a finite field has multiplicative order exactly $n$. If $p\mid n$, no such element exists, since all roots have order dividing $m<n$. If $\gcd (n,q)=1$, choose a generator $\zeta$ of $E(n,q)$. The element ${\zeta }^j$ has order $n/\gcd (n,j)$, so it is primitive precisely when $\gcd (n,j)=1$. Therefore there are $\phi (n)$ primitive roots, with $\phi$ the Euler totient function.

If $\omega$ is primitive of order $n$, then $\omega \in {\mathbb{F}}_{q^{\ell }}$ exactly when ${\omega }^{q^{\ell }}=\omega$, equivalently $n\mid q^{\ell }-1$. The implication from that equality to membership follows because the roots of $T^{q^{\ell }}-T$ form ${\mathbb{F}}_{q^{\ell }}$, as proved in the preceding solution. Consequentlyfor $n>1$, and the degree is one for $n=1$. This is also the length of the finite-field Frobenius automorphism orbit of $\omega$.

Using the same $(1,u)$ basis of ${\mathbb{F}}_9$ as before, the fourth roots of unity areThere are four, they are already in ${\mathbb{F}}_9$, and the primitive fourth roots are the two vectors $(0,1)$ and $(0,2)$.

A central application is quantum order finding, which supplies the quantum step in the Shor algorithm for factoring an integer $M$. Choose an integer $a$ coprime to $M$, and let $r$ be its multiplicative order modulo $M$. On valid residue quantum states define the reversible modular-multiplication unitary operator $U_a|x⟩=|ax\mathrm{mod}M⟩$, extending it reversibly to any unused computational basis quantum states.

The orbit $|1⟩,|a⟩,\dots ,|a^{r-1}⟩$ has the orthonormal eigenstatesfor $s=0,\dots ,r-1$. One need not know $r$ to prepare an eigenstate: the easy input $|1⟩=r^{-1/2}{\sum }_s|u_s⟩$ makes quantum phase estimation sample one of these eigenphases. Its control register estimates $s/r$. With $N=2^t$ chosen at least of order $M^2$, the nearest quantum phase label has rational approximation error small enough for continued-fraction recovery in quantum order finding. For instance, $N>2M^2$ gives $|m/N-s/r|<1/(2r^2)$ on the nearest-label event. If $s$ and $r$ are coprime, the recovered denominator is $r$; otherwise one obtains a divisor and can repeat, combine candidates and verify them by modular exponentiation.

When the verified order is even and $a^{r/2}\not\equiv -1(\mathrm{mod}M)$, the greatest common divisorsgive nontrivial factors: their product is divisible by $M$, while neither factor inside the gcd is zero modulo $M$. Unsuccessful choices of $a$ or quantum phase samples are handled by repetition and classical verification. Controlled powers of $U_a$ are implemented by efficient reversible modular arithmetic, rather than by naively applying $U_a$ exponentially many times.

Quantum phase estimation turns modular-multiplication eigenphases into an efficiently usable period, enabling quantum factoring in time polynomial in the bit length of the integer. Factoring is important to public-key cryptography, and this is a major example of a quantum algorithm improving on known classical methods. Another use is extracting energy eigenvalues by applying quantum phase estimation to a controlled time-evolution operator, with care to avoid energy aliasing and to prepare an input having overlap with the desired eigenstate.

Let $g$ generate the cyclic group of nonzero residues, whose order $p-1=2^{2^n}$ is a power of two. Write $a=g^j$. Its multiplicative order is $(p-1)/\gcd (j,p-1)$, so it is a primitive root precisely when $j$ is odd. The quadratic residues are exactly the even powers of $g$. Thus the primitive roots are precisely the quadratic nonresidues, with nonzero residue classes understood.

For $n\ge 1$, $p\equiv 1(\mathrm{mod}4)$, so quadratic reciprocity gives $(7/p)=(p/7)$. Since $2^3\equiv 1(\mathrm{mod}7)$ and $2^n$ alternates between $1$ and $2$ modulo three, $p$ is respectively $3$ or $5$ modulo seven. The nonzero squares modulo seven are $1,2,4$. Consequently $(7/p)=-1$, andThere is a genuine endpoint exception if the printed form permits $n=0$: then $p=3$ and $7\equiv 1(\mathrm{mod}3)$, which has order one and is not primitive. The first equivalence remains true for $p=3$, but the final assertion requires excluding that prime.

The requested representation is the left coset actionIt is well defined because equal cosets remain equal after multiplication by $g$, and $\rho (g{g}^{\prime })=\rho (g)\rho (g^{\prime })$. It is transitive. For $H=1$ it is the left regular action; for general $H$ it is the associated transitive coset representation.

Its kernel is the normal core of a subgroupIndeed, $g$ fixes every $xH$ precisely when $x^{-1}gx\in H$ for every $x$. Thus $N⊲G$ and $N\le H$. If $[G:H]=i<\infty$, the image lies in the finite symmetric group $S_i$, soIn particular $N$ has finite index in $H$.

For Higman group as an amalgam of iterated HNN extensions, use the cyclic squaring presentationFirst form $L=⟨b,c\mid b^{-1}cb=c^2⟩$, an HNN extension of the infinite cyclic group $⟨c⟩$. Its base embeds, so $c$ has infinite order; $b$ has infinite order as well, since the homomorphism $L\to \mathbb{Z}$ sending $b\mapsto 1,c\mapsto 0$ is onto. Consequently $⟨b⟩$ and $⟨b^2⟩$ are isomorphic infinite cyclic subgroups. Adjoining the stable letter $a$ with $a^{-1}ba=b^2$ givesWe claim $⟨a,c⟩$ is a rank-two free group. No nonzero power of $c$ belongs to $⟨b⟩$: applying the map $b\mapsto 1,c\mapsto 0$ would make that power equal to $1$, contradicting the infinite order of $c$. Thus no nonzero power of $c$ belongs to $⟨b^2⟩$ either. Any nonempty freely reduced word in $a,c$ that contains $a$ is therefore a reduced HNN sequence: between inverse $a$ letters, a nonzero $c$ power cannot create a pinch. Britton's lemma makes it nonidentity. A word containing only $c$ is nonidentity by the base embedding. This proves the claim.

Likewiseis obtained from $⟨d,a\mid d^{-1}ad=a^2⟩$ by adjoining $c$, and its subgroup $⟨c,a⟩$ is free of rank two by the same argument. Form the amalgamated free product $P{\ast }_{⟨a,c⟩}Q$, identifying these two free subgroups generator by generator. Its presentation is exactly that of $\mathcal{H}$. The component embeddings allowed in the question show that it contains $P$, hence is infinite. It has four group generators and four relators, so it is finitely presented.

To show that this Higman group has no nontrivial finite quotient, consider any finite image and the orders of the four generator images. A relation $x^{-1}yx=y^2$ makes $y$ and $y^2$ have the same order, so every generator order is odd. Suppose one is nontrivial, and let $p$ be the smallest prime dividing any of the four orders. Choose a generator $y$ whose order is divisible by $p$, with predecessor $x$ satisfying the displayed relation. Iterating conjugation $|x|$ times givesThe multiplicative order $d$ of $2$ modulo $p$ thus divides $|x|$. Also $d\mid p-1$ and $d>1$, since $2\not\equiv 1(\mathrm{mod}p)$. Any prime divisor of $d$ is smaller than $p$ and divides the order of $x$, contradicting minimality of $p$. Hence every generator image is trivial, so every finite image is trivial. A proper finite-index subgroup would give a nontrivial transitive finite coset image, which is impossible. Therefore $\mathcal{H}$ is infinite and finitely presented, with no proper finite-index subgroups.

A maximal normal subgroup is a proper normal subgroup $M⊲G$ with no normal subgroup strictly between $M$ and $G$. To prove that finitely generated groups have maximal proper normal subgroups, fix a proper normal subgroup $K$ and order the proper normal subgroups containing $K$ by inclusion. For a chain, its union is normal and contains $K$. It is still proper: if the union were all of $G$, each element of a finite generating set would lie in some chain member, and the chain order would put all these finitely many group generators in one member. That member would equal $G$, a contradiction. The Zorn lemma therefore supplies a maximal proper normal subgroup $M$ containing $K$.

Apply this to $\mathcal{H}$ and $K=1$. By the normal-subgroup correspondence, $\mathcal{H}/M$ is nontrivial and simple. It is finitely generated as a quotient of $\mathcal{H}$. It cannot be finite, since $\mathcal{H}$ has no nontrivial finite quotients. Thus

The final assertion for arbitrary proper subgroups is false. Take $G=S_3$ and $H=⟨(12)⟩$. If a normal subgroup contained $H$, it would contain all conjugate transpositions, which generate $S_3$, so it would equal $G$. Hence this proper subgroup lies in no proper normal subgroup, and in particular in no maximal normal subgroup. The maximal-normal existence result requires the starting subgroup itself to be normal.