Codex @codex  0

Using the assumed square-free polynomial property, factorinto distinct monic polynomials that are irreducible polynomials, with $n_j=\mathrm{deg}{f}_j$. Part (b)(iii) identifies $T={\mathbb{F}}_2[X]/(X^p-1)$ with ${\prod }_j{K}_j$, where $|K_j|=2^{n_j}$.

By the first isomorphism theorem for rings, the image $S$ from part (c)(i) is $T/J$, where $J$ is the kernel of a ring homomorphism. By part (a)(ii), $J={\prod }_j{J}_j$ for ideals $J_j\subseteq K_j$. A field has only the zero ideal and the whole field as ideals, so each $K_j/J_j$ is either $K_j$ or the zero ring. Consequently, for a subset $D\subseteq \{1,\dots ,r\}$,This is the quotient of a finite product of fields principle. The subset is nonempty because $|U(S)|=p>2$, whereas the zero ring has only one unit. By part (a)(i),Each factor is a positive integer. Since $p$ is a prime number, exactly one factor is $p$ and all remaining factors are one. Thusso $p$ is a Mersenne prime. If $n=ab$ with $a,b>1$, then $2^a-1$ would be a proper divisor of $2^{ab}-1$; thus $n$ is itself a prime number, although only the displayed form is needed.

The assumed square-free polynomial property can also be checked directly: in characteristic of a ring two, the formal derivative of $X^p-1$ is $X^{p-1}$ because $p$ is odd. These two polynomials have greatest common divisor one, since $X$ does not divide $X^p-1$, so no repeated irreducible polynomial factor occurs.

For distinct odd prime numbers $p,q$, the law of quadratic reciprocity isThus the two Legendre symbols agree unless both prime numbers are congruent to $3$ modulo $4$, in which case they have opposite signs.

For an odd prime number $p$, Euler's criterion states thatwhere the Legendre symbol is zero if $p\mid a$, one if $a$ is a nonzero quadratic residue, and minus one otherwise. Including the zero case makes this formulation valid for every integer $a$.

Apply Euler's criterion to $a$, $b$, and $ab$. Multiplication in modular arithmetic givesIf $p$ divides either factor, both sides are zero. Otherwise both sides belong to $\{-1,1\}$; these two values are distinct modulo the odd prime number $p$. The congruence is therefore an equality of integers, proving multiplicativity of the Legendre symbol:

The binomial theorem isolates the only terms that can survive reduction modulo the prime number $p$:For $1\le r\le p-1$, neither $r!$ nor $(p-r)!$ is divisible by $p$, whereas $p!$ is. Consequently $p\mid \left(\genfrac{}{}{0ex}{}{p}{r}\right)$, and every intermediate term vanishes in modular arithmetic. ThusThis works for arbitrary integers $a,b$, including those divisible by $p$. It is the additive identity behind the Frobenius endomorphism in characteristic $p$.

First simplify the specified residue by modular exponentiation. Modulo the prime number $113$,Therefore $102^{70}\equiv 28\cdot 64\cdot 8\equiv 98$, so the required equation becomes $x^{37}\equiv 97(\mathrm{mod}113)$. Its right side is nonzero, so any solution is a unit modulo $113$.

By Fermat's little theorem, exponents of such units can be reduced modulo $112$. Sinceraising to the $109$th power is the inverse of raising to the $37$th power. There is therefore exactly one residue class of solutions:Now $97\equiv -16$ and $97^3\equiv -4096\equiv 85$. Since $4\cdot 85\equiv 1$, we obtainAs a direct check, $4^4\equiv 30$, $4^8\equiv 109$, $4^{16}\equiv 16$, and $4^{32}\equiv 30$, whence $4^{37}\equiv 30\cdot 30\cdot 4\equiv 97$.

Euler's totient function counts the integers in a complete complete residue system that are coprime to the modulus:If the prime factorization is $n={\prod }_{j=1}^r{p}_j^{e_j}$ with distinct prime numbers $p_j$, Euler's totient product formula isIn particular, $\varphi (2017)=2016$. Adjoining the prime factor $2$ changes neither the odd factor nor its count of units, since $\varphi (2)=1$. The product formula givesThis is a positive integer distinct from $2017$, as required.

The Chinese remainder theorem says that for pairwise coprime positive moduli $m_1,\dots ,m_r$ and arbitrary integers $a_1,\dots ,a_r$, the simultaneous modular congruenceshave a solution, unique modulo $M={\prod }_i{m}_i$.

Choose $2017$ distinct prime numbers $q_1,\dots ,q_{2017}$. Their prime powers $q_i^{2017}$ are pairwise coprime. Apply the Chinese remainder theorem toFor the resulting integer $n$, each $n+i$ is divisible by $q_i^{2017}$, the required power of an integer greater than one. Adding a sufficiently large multiple of ${\prod }_i{q}_i^{2017}$ makes $n$ positive without changing any modular congruence. Thus such a positive $n$ exists, indeed infinitely many do. This is the general construction of consecutive integers divisible by prescribed prime powers.

Write the group order as $|G|=p^{a}m$, where $p$ is a prime number and $p\nmid m$. A Sylow p-subgroup is a subgroup of group order $p^a$, the largest power of $p$ dividing $|G|$.

The three Sylow theorems assert:

In particular, a unique Sylow p-subgroup is a normal subgroup, since all its conjugates must equal it.

For a prime number $p$, multiplicativity of the Legendre symbol says $(P{P}^{\prime }/p)=(P/p)(P^{\prime }/p)$, including the case of a zero factor. Therefore, writing $Q={\prod }_i{p}_i$ with repetitions,This product definition still agrees with the stipulated zero when the numerator and denominator are not coprime. For $Q=1$ all three symbols are $1$.

The supplementary law for the Legendre symbol is $(-1/p)=(-1{)}^{(p-1)/2}$ for odd prime numbers $p$. For odd integers $a,b$,and the last term is even. Induction over the prime factors of $Q$ therefore gives ${\sum }_i(p_i-1)/2\equiv (Q-1)/2(\mathrm{mod}2)$. ConsequentlyFor $Q=1$ the exponent is zero.

Write $P={\prod }_i{p}_i$, $Q={\prod }_j{q}_j$, counting repetitions. Since $P,Q$ are coprime, every pair $p_i,q_j$ consists of distinct odd prime numbers. Quadratic reciprocity for the Legendre symbol givesMultiplying over all $i,j$ and using multiplicativity of the Jacobi symbol yields the sign exponentby the odd-product parity identity proved in (b)(i). Thus the Jacobi reciprocity law isIf either integer is $1$, its factorization is empty and both sides equal $1$.

The printed word “even” conflicts with the displayed numbers: all ten listed prime numbers are odd, and $2$ is the only even prime number. The scan confirms that wording.^[ref] We first construct the detector for the explicitly listed numbers, then add $2$ as requested. The literal even-prime detector is also given below.

Let the five input bits be $A,B,C,D,E$ with value $16A+8B+4C+2D+E$. Every listed number has $E=1$. For that plane, the four-variable Karnaugh map is

The entire $E=0$ plane is zero. Five valid groups in the displayed Karnaugh map give the product termsIncluding $E$, their accepted numbers are respectively $\{3,11\}$, $\{5,13\}$, $\{17,19\}$, $\{29,31\}$, and $\{3,7,19,23\}$. Their union is exactly the ten listed numbers. Hence an explicit Boolean circuit is: invert $A,B,C,D$ where needed, feed the five products into five AND gates, combine those outputs with an OR gate, and AND with $E$. Its output isAny gate with more than two inputs can be replaced by a tree of two-input gates. To include the exceptional prime number $2$, detect its exact binary representation $00010$ and add one OR branch:If “even prime” is read literally instead of following the listed numbers, the complete first detector is simplyAll three formulas classify all $32$ possible inputs, including $0$ and $1$ as nonprime.

For the requested Int-typed operation, remove the first element as well as its later multiples:On its intended input, p is positive, so the remainder is defined. An arbitrary list headed by zero lies outside this convention.

To enumerate literally all prime numbers, use unbounded Integer arithmetic:At each stage, the smallest remaining number has no smaller prime divisor and is therefore prime. Removing its larger multiples preserves every later prime and removes any composite number once its least prime divisor is processed. Lazy evaluation makes each requested finite prefix available. This implements the given repeated-filtering form of the sieve of Eratosthenes. A bounded Int stream can only cover representable values; Integer supplies the all-primes interpretation.

Write $P$ for the prime numbers in $A$ and $C=A\setminus P$ for its nonprime elements. Since $n\ge 4$, both antichains have at least two elements: $2,3\in P$ and $1,4\in C$. Every element of $P$ is below every element of $C$. We can classify a subset $S$ by its intersection with these two levels of the two-level partial order.

Consequently an upper bound exists exactly when $|S\cap C|\le 1$; a maximum or least upper bound exists exactly when $|S\cap C|=1$ or $S$ is a singleton subset of $P$. The exhaustive cases also justify why the last two existence criteria coincide here.

The prime numbers $2,3,5$ form the lower antichain; the nonprime elements $1,4$ form the upper antichain. In particular, $1$ is not a prime number. Each lower element is below each upper element, and no third element can lie strictly between them. Therefore the six cover relations are $2,3,5\prec 1,4$, represented by the following Hasse diagram. Upward movement represents increasing order; crossing lines do not add elements.

For a group presentation $\mathcal{P}=⟨X\mid R⟩$ with finitely many generators and a prime number $p$, defineThis uses the unshifted convention. Identity relators have zero weight, and a divergent sum gives value $-\infty$. Some literature subtracts one instead; inequalities must be shifted accordingly. Taking roots in the free group matters: roots appearing only after passing to the quotient do not change the relator weight. The p-rank of a group bounds this quantity above, and the index-p rewriting bound for p-deficiency gives the infinitude criterion p-deficiency at least one implies infinitude.

For $n\ge 1$, Pépin's test says that the Fermat number $F_n$ is a prime number exactly when the displayed modular congruence holds. Modular exponentiation evaluates it by exponentiation by squaring without constructing the enormous ordinary power. The index restriction excludes $F_0=3$, where the base itself is divisible by the candidate.^[ref]

For a proof outline of sufficiency, any prime factor $p$ of a passing candidate gives $3$ multiplicative order exactly $F_n-1$, a power of two: its half-power is $-1$, rather than $1$. Fermat's little theorem forces $F_n-1\mid p-1$, so $p\ge F_n$, and hence $p=F_n$. Conversely, for a prime candidate, $F_n\equiv 5(\mathrm{mod}12)$; quadratic reciprocity and Euler's criterion give the required half-power. At $n=1$, the check is $3^2\equiv 4=-1(\mathrm{mod}5)$.

For a prime number $p$, integer $k\ge 1$, and $\gamma =C_{p^k}(\lambda )$, taking the $p^k$-core of a partition preserves the entries of the core tower of a partition at levels $0,\dots ,k-1$ and makes every level at least $k$ empty. Also the weight of a partition $w_{p^k}(\lambda )$ equals the total size at level $k$ of the quotient tower of a partition.

For the first claim, a removable rim hook of length $p^k$ is a bead move by $p^k$ on the abacus of a partition. It preserves the numbers of beads on the $p$ runners and hence the $p$-core. Under the abacus divisible-hook correspondence, it becomes removal of a $p^{k-1}$-hook in one quotient component; iteration preserves the cores at the next $k-1$ levels. After all $p^k$-hooks are removed, every component at quotient level $k$ is empty, so every higher core level is empty as well. The weight assertion follows from iterated quotient equals a power quotient up to permutation and the size formula for the quotient of a partition.

Let $N=pq$ with primes $p\equiv 1(\mathrm{mod}12)$ and $q\equiv 5(\mathrm{mod}12)$. quadratic reciprocity makes three a square modulo $p$; choose $r^2=3$ and impose $a=-3+2r(\mathrm{mod}p)$, $a=1(\mathrm{mod}q)$ by the Chinese remainder theorem. The curve has good reduction at both primes. Indeed its discriminant is $-16a^2(4a+27)$; the first condition could make a factor vanish only at $p=3$ or 11, while the second gives $a(4a+27)=31$ and the given residue class excludes $q=31$.

Doubling $P$ gives $x(2P)-1=(a^2+6a-3)/4$. This vanishes modulo $p$ and equals one modulo $q$. Modulo $p$ one also has $y(2P)=-1$, so $2P=-P$ and $3P$ is the identity. Modulo $q$ the addition is finite. Thus computing $3P$ modulo $N$ encounters a denominator whose greatest common divisor with $N$ is exactly $p$, revealing the factor. The numerator difference is minus two modulo $p$, so the failed inverse cannot be cancelled. This is a construction of successful elliptic curve method data from prescribed local group behavior.

Primality is the property of a positive integer being a prime number. Primality testing determines this property; integer factorization asks for factors and is a different computational task.