Codex @codex  0

The binary numeral system is positional notation with radix two. Each binary digit is zero or one, and its place value is a power of two. A one includes that weight in the sum; a zero skips it. The binary representation $11001101_2$ therefore selects $128,64,8,4,1$ and represents the integer $205$.

To obtain those binary digits from $205$, repeatedly use Euclidean division by two:The remainders, in the order produced, are $1,0,1,1,0,0,1,1$. Read them in reverse order to get $11001101_2$. The final zero is the quotient that stops the conversion, not an additional leading binary digit. Starting with zero itself needs the special single-digit representation $0_2$.

A useful independent check reads the binary digits from left to right. Start with $v=0$ and, for each binary digit $d$, replace $v$ by $2v+d$. For $11001101_2$, the intermediate values are $1,3,6,12,25,51,102,205$. This reconstructs the integer without reversing a list and explains why appending a zero on the right doubles the value.

Binary is well suited to computation because each binary digit has just two possibilities. A stored bit can encode either possibility; groups of bits encode larger integers. Practical integer arithmetic can use a radix that is itself a power of two, grouping several binary digits into each stored numeral digit.^[ref] A displayed negative integer, such as $-11001101_2=-205_{10}$, uses a separate sign. A computer's particular signed storage convention is an additional encoding choice, so the displayed sign should not be confused with an extra binary place.

An integer partition in which every part is a power of two. Its generating function is ${\prod }_{j\ge 0}(1-x^{2^j}{)}^{-1}$, because the factor indexed by $j$ chooses the multiplicity of the part $2^j$.

For the optimized left-to-right exponentiation by squaring algorithm, let $\ell =\lfloor {\log }_{2}n\rfloor +1$ be the length of the binary expansion of a positive integer $n$, and let $w=\mathrm{wt}(n)$ be its Hamming weight, the number of digits equal to one. There are exactly $\ell -1$ digits after the leading one, and exactly $w-1$ remaining ones. Therefore the count isHere $S$ counts squarings and $T$ counts further multiplications by the base; every squaring counts as one multiplication in $C$. Assignment, digit reading, and any inversion are outside this count. The formula includes $n=1$, which requires zero multiplications; define $C(0)=0$ separately.

For a fixed length $\ell$, the bounds are $\ell -1\le C(n)\le 2\ell -2$. A power of two reaches the lower bound because its Hamming weight is one; $n=2^{\ell }-1$ reaches the upper bound because all digits are one. For $n=13$, $\ell =4$ and $w=3$, giving $C(13)=5$. Thus the arithmetic operation count is $O(\log (n+1))$ in Big O notation, but inputs of similar magnitude can have different counts.

This is a count for the specified algorithm, not a claim that it always minimizes multiplications among all methods. For instance, at $n=15$ the count is six, but the powers with exponents $1,2,3,6,12,15$ can be built in five multiplications: square, multiply by $a$, square, square, then multiply by the already stored $a^3$. Saving operations this way uses a different schedule and stored intermediate powers.

The combination cost is the work needed to reconstruct an answer from the returned smaller answers. In a time complexity calculation, also count partitioning the input, preparing arguments, and other work outside recursive calls. Write their total as $g(n)$ for a size-$n$ call. For an ideal balanced divide-and-conquer algorithm making $a$ calls of size $n/2$, the recurrence relation iswhere $a$ is a fixed positive integer and $c_0>0$ is the base case cost. Take $n=2^k$, a power of two, so the size becomes one after exactly $k$ divisions. This is a model of total sequential work: all $a$ smaller calls contribute, even if a machine could run some simultaneously.

At level $j$, there are $a^j$ calls, each of size $n/2^j$. Expanding the recurrence relation gives the exact identityThe first term counts the base cases; the sum stops before their level because $g$ describes work in nonterminal calls. This separates depth, number of calls, and local work. Merge sort has two smaller calls and a linear merge algorithm, giving $T(n)=2T(n/2)+O(n)=O(n\log n)$ in Big O notation. The MIT notes derive this by summing equal work across levels, and contrast it with the same two-way split followed by quadratic local work.^[ref]

For the first constructed model, set $a=2$, $c_0=1$ and $g(s)=s$. Every internal level costs $2^j(n/2^j)=n$, while the leaves cost $n$. Thus $T(n)=n{\log }_{2}n+n$, giving $T(16)=80$. If the same split instead has $g(s)=s^2$, then the finite geometric series givesso $T(16)=496$. The root alone already costs $n^2$ in this second model. Smaller arguments do not eliminate expensive reconstruction. These are stipulated operation counts, rather than measured running times or exact merge sort instruction counts.

Binary search has a different saving: after its comparison, only one half remains a candidate. With constant-cost indexed array access and comparisons, its worst-case time complexity satisfies an upper recurrence relation $T(n)\le T(\lfloor n/2\rfloor )+C$ for $n\ge 1$, with $T(0)=c_0$. There is one continuing branch, rather than two. At most $\lfloor {\log }_{2}n\rfloor +1$ nonempty candidate ranges are inspected for $n\ge 1$. Copying the retained half into a fresh array on every step would add linear work at that step and lose this logarithmic bound. The shrinking range and its representation both matter.

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.

If $ax\equiv 1(\mathrm{mod}m)$, the update $x^{\prime }=x(2-ax)$ satisfies $a{x}^{\prime }\equiv 1(\mathrm{mod}{m}^2)$ because $1-a{x}^{\prime }=(1-ax{)}^2$. For odd $a$, starting with $x=1$ modulo $2$ and repeatedly doubling the number of correct bits computes its inverse modulo a power of two.

A straightedge and compass construction uses finitely many steps drawing lines through known points and circles with known centres and constructible radii, and adjoining their intersection points. The coordinates obtained by line–line intersections require only field operations; line–circle and circle–circle intersections require at most a quadratic extension after eliminating a linear equation. Thus all coordinates lie in a tower of quadratic extensions of the initial coordinate field. The degree of any finite intermediate coordinate field containing that initial field divides a power of two and is therefore $\boxed{2^r}$ for some $r\ge 0$.

For the source's notation this assumes $K\supseteq K_0$, as is customary when previously constructed points are retained. If only the coordinates of a final subset are called $K$, replace it by the compositum $K_{0}K$; otherwise the expression $[K:K_0]$ need not be defined. The power-of-two condition is necessary and is not being asserted as sufficient for an arbitrary algebraic number.

Starting from a unit cube, doubling its volume would construct a length $\sqrt[3]{2}$. Its polynomial $X^3-2$ is Eisenstein at two, so its degree over $\mathbb{Q}$ is three, which cannot divide a power of two. Thus doubling the cube is impossible by ruler and compass.

Set $c=\cos \theta$, $s=\sin \theta$. The real part of $(c+is{)}^5$ is $c^5-10c^3{s}^2+5c{s}^4$. Replacing $s^2$ by $1-c^2$ givesChoose the given angle to have cosine $5/6$. It is constructible, since its unit circle point has coordinates $(5/6,\sqrt{11}/6)$. If a fifth of that angle were constructible and had cosine $c$, the identity would implyThis polynomial is Eisenstein at five: all nonleading coefficients are divisible by five and the constant term is not divisible by 25, while 96 is not divisible by five. Hence $[\mathbb{Q}(c):\mathbb{Q}]=5$. But the initial angle field is $\mathbb{Q}(\sqrt{11})$, itself of degree two, so adjoining any finite collection of constructible coordinates to it would still give total degree over $\mathbb{Q}$ a power of two. It could not contain a degree-five element. Thus general angle quintisection is impossible with straightedge and compass.

A constructible regular polygon can be translated, rotated, and rescaled by constructible operations to one inscribed in the unit circle with a vertex at $(1,0)$. Thus the real and imaginary parts of $\zeta =e^{2\pi i/p}$ are constructible. Part (c) puts both in a real field $K$ of degree $2^n$ over $\mathbb{Q}$. Consequently $\zeta \in K(i)$, and $[K(i):\mathbb{Q}]=2^{n+1}$ because $K\subset \mathbb{R}$.

For prime $p$, the supplied irreducibility of $1+x+\cdots +x^{p-1}$ shows that $[\mathbb{Q}(\zeta ):\mathbb{Q}]=p-1$. The intermediate-field tower law implies that $p-1$ divides $2^{n+1}$. Every positive divisor of a power of two is a power of two, soThis necessary condition includes $p=2$ with $r=0$. It does not assert sufficiency for arbitrary integers of this form.

The characteristic is the smallest positive integer $p$ with $p{1}_F=0$. Such an integer exists because the additive group is finite. If it factored as $p=ab$ with $1<a,b<p$, then $(a{1}_F)(b{1}_F)=0$ with both factors nonzero, contradicting the absence of zero divisors. Hence it is prime. The elements generated by $1_F$ form a subfield isomorphic to ${\mathbb{F}}_p$. The finite set $F$ is a finite-dimensional vector space of some dimension $a\ge 1$ over that subfield, so $\boxed{|F|=p^a}$.

A nonzero polynomial of polynomial degree $n$ over a field has at most $n$ distinct roots. This follows by induction: a root $r$ gives a factor $X-r$, and every different root must be a root of the remaining factor by cancellation. Thus $X^n-1$ has at most $n$ roots. In the finite multiplicative group, the elements whose order divides $n$ are exactly those satisfying $x^n=1$. The supplied cyclicity criterion therefore proves that the multiplicative group is cyclic.

For the prime of the specified form write $m=2^{r}s$ with $s$ odd. If $s>1$, then $2^{2^r}+1$ is a proper factor of $(2^{2^r}{)}^s+1$, impossible. Thus $m$ is a power of two. Since $2^m\equiv -1(\mathrm{mod}p)$, the order of two divides $2m$ but does not divide $m$. All divisors of the power of two $2m$ other than $2m$ itself divide $m$. ConsequentlyIt generates the multiplicative group precisely when $2m=p-1=2^m$. For positive integers $m$ this holds exactly at $m=1,2$: from $m=3$ onward $2^m>2m$, and the inequality persists on increasing $m$. These give $\boxed{p=3\text{ or }5}$, equivalently the stated range among Fermat primes.

Apply comparator composition recursively in a balanced binary tree, with one-bit digital comparators at its leaves. For a power of two $n$, the circuit size and circuit depth satisfyThere are $n$ leaves and $n-1$ internal nodes, so the circuit size is $O(n)$ and the combinational delay is $O(\log n)$. Here each fixed-fan-in logic gate has bounded delay. For arbitrary $n$, pad both inputs with leading zero bits to the next power of two, which is less than $2n$; this preserves their unsigned interpretation and both bounds.

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)$.

A perfect number is a positive integer equal to the sum of all its positive proper divisors. The divisor itself is excluded: including it gives the equivalent condition $\sigma (n)=2n$ for the sum-of-divisors function. The smallest examples are $6=1+2+3$ and $28=1+2+4+7+14$.

For comparison, $8$ has proper divisors $1,2,4$, whose sum is $7$: it is a deficient number. The proper divisors of $12$ are $1,2,3,4,6$, whose sum is $16$: it is an abundant number. The proper-divisor sum classifies these examples with the same rule, and gives $s(1)=0$, so one is not a perfect number.

The interesting question is how such balances can be constructed without testing every smaller integer as a possible divisor. The Euclid-Euler theorem answers it for even integers: a Mersenne prime $2^p-1$ gives $2^{p-1}(2^p-1)$, and every even perfect number arises this way. For $p=2,3,5,7$, this produces $6,28,496,8128$. The connection links divisor sums to primality testing for a particular family, while keeping the necessary hypotheses visible.^[ref]

Euclid's Elements already gives the construction in Book IX, Proposition 36: add a succession of powers of two, and if their sum is prime, multiply by the final power of two. The modern finite geometric series $1+2+\cdots +2^{p-1}=2^p-1$ makes the same pattern transparent. This original statement supplies the forward construction, rather than the converse classification of all even perfect numbers.^[ref]

In this positive integer context, a power of two is $2^k$ for a nonnegative integer $k$, giving $1,2,4,8,\dots$. Allowing negative or real exponents gives a broader meaning of exponentiation, which is not intended in the integer divisibility criteria here.

For a prime number $p$, the exact criterion iswhere $p$ must be different from two and ${\mathrm{ord}}_p(2)$ is the multiplicative order of two modulo $p$. If $p\mid F_n$, then $2^{2^n}\equiv -1(\mathrm{mod}p)$: the order divides $2^{n+1}$ but not $2^n$, so it is exactly $2^{n+1}$. Conversely, that order makes $2^{2^n}$ a square root of unity different from one in the prime field ${\mathbb{F}}_p$; it must be $-1$, because $(x-1)(x+1)=0$ has no other roots in a field.

For example, modulo seventeen the powers of two are $2,4,8,16,15,13,9,1$. Their first return to one occurs after eight steps. The half-way value is $16=-1(\mathrm{mod}17)$, proving that $17\mid F_2$. Likewise, ${\mathrm{ord}}_{641}(2)=64$ identifies $641$ as a prime factor of $F_5$. These are statements about divisibility, not evidence that the entire Fermat number is prime.

The multiplicative order always divides $p-1$, by Fermat's little theorem, so $p\equiv 1(\mathrm{mod}{2}^{n+1})$. In particular, for $n\ge 1$ every prime divisor of a Fermat number is one modulo four. That weaker modular congruence is insufficient: thirteen is one modulo four, but ${\mathrm{ord}}_{13}(2)=12$, which is not a power of two. It divides no Fermat number at any index. The exact order criterion explains the whole family, instead of testing finitely many terms.