The Gaussian integers form an integral domain, since they are a subring of the complex numbers. Use the Gaussian integer norm
which is a positive integer for nonzero and satisfies .
For with , write . Choose integers with and , put , and set . Then
Thus division with remainder has either or a strictly smaller Gaussian integer norm. This proves that is a Euclidean function and
Each entry of the matrix from part (b)(iii) has unique real and imaginary integer coefficients. Write
It already belongs to the general linear group . Expanding the relation from part (b)(iii) gives
The real and imaginary parts must both vanish, so
These are the required identities, with .
Euler's criterion states, for an odd prime ,
Apply it to . The integer is when and when . Since those signs are distinct modulo an odd prime, the modular congruence determines the actual Legendre symbol:
This is the first supplementary law for quadratic reciprocity.
For an odd prime , the Legendre symbol is
It depends only on the congruence class of the integer . The values and distinguish a nonzero quadratic residue from a quadratic nonresidue; zero is a separate case.
Choose any pair from part (i), and put . The divisibilities of the exponents make
positive integers. Their powers are
Thus , with all three powers nonzero and distinct. For example, take , for every nonnegative integer . Then strictly increases, giving infinitely many distinct solutions. The construction uses modular congruences to turn the elementary identity into three prescribed perfect powers.
Writing , the second condition becomes . Writing , its second condition becomes . Consequently
gives an infinite set of positive integer solutions. Conversely these are the positive solutions in the indicated congruence classes, by the Chinese remainder theorem.
The Ramsey number is the least positive integer such that every red-blue coloring of the edges of has a red or a blue . Equivalently, every -vertex graph has a clique of size or an independent set of size .
For , either there is a blue edge or every edge is red, producing the red . Conversely an entirely red has neither a red nor a blue edge. Therefore
For an odd prime number , Euler's criterion states that
where the Legendre symbol is zero if , one if is a nonzero quadratic residue, and minus one otherwise. Including the zero case makes this formulation valid for every integer .
Apply Euler's criterion to , , and . Multiplication in modular arithmetic gives
If divides either factor, both sides are zero. Otherwise both sides belong to ; these two values are distinct modulo the odd prime number . 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 :
For , neither nor is divisible by , whereas is. Consequently , and every intermediate term vanishes in modular arithmetic. Thus
This works for arbitrary integers , including those divisible by . It is the additive identity behind the Frobenius endomorphism in characteristic .
Euler's totient function counts the integers in a complete complete residue system that are coprime to the modulus:
If the prime factorization is with distinct prime numbers , Euler's totient product formula is
In particular, . Adjoining the prime factor changes neither the odd factor nor its count of units, since . The product formula gives
This is a positive integer distinct from , as required.
The Chinese remainder theorem says that for pairwise coprime positive moduli and arbitrary integers , the simultaneous modular congruences
have a solution, unique modulo .
Choose distinct prime numbers . Their prime powers are pairwise coprime. Apply the Chinese remainder theorem to
For the resulting integer , each is divisible by , the required power of an integer greater than one. Adding a sufficiently large multiple of makes positive without changing any modular congruence. Thus such a positive exists, indeed infinitely many do. This is the general construction of consecutive integers divisible by prescribed prime powers.
The radial S wave vanishes at the hard surface, so outside the sphere . Comparison with gives
The hard-sphere S-wave scattering amplitude and cross section are therefore
The three prominent features are the finite low-energy limit , the oscillations with exact zeros at for positive integers , and the decreasing envelope . The zero-energy value is four times the geometric area . Near zero the normalized cross section is . The large- fall here concerns the S wave alone; summing all partial waves gives a different high-energy total.
Figure 1.
Hard-sphere S-wave cross-section and delta-shell Born angular scattering
. Dimensionless curves calculated directly from the derived scattering amplitudes. The left panel concerns only the S wave, while the right panel shows different incident wave numbers for the weak delta-shell model. Details.
For integers ,
Thus reducing coordinates modulo one gives a well-defined function on the torus . Its determinant is one and its inverse matrix is the integer matrix , so it induces a bijection of the torus. The Jacobian determinant one makes this bijection area-preserving.
Its eigenvalues solve , giving
There are therefore expanding and contracting eigendirections and no eigenvalue on the unit circle: the function is a hyperbolic toral automorphism. The Lyapunov exponents per iterate are
They sum to zero, as required by area preservation.
The four vertices of the unit square map to , the vertices of an area-one parallelogram. To reduce it modulo one, cut it by the integer grid. For each piece in the cell , translate by . Up to boundary identifications these translated pieces partition the unit square, because the inverse integer matrix gives exactly one torus preimage to every point. The colored pieces in the original diagram show the same pieces before and after these translations.
Figure 1.
Area-preserving torus map by cutting and translating its parallelogram
. Details.
For the Fibonacci identity, at the claimed matrix is . If the identity holds at , multiplication on the right by gives
Each equality uses , with the specified indexing . This proves the formula for every positive integer .
A fixed point satisfies . Since has an inverse integer matrix, this forces , so the origin is the only fixed point modulo one.
For period dividing two,
The second congruence gives ; inserting it into the first gives . Thus the complete list is
The first is the fixed origin. Direct application of exchanges the other four in exactly two pairs:
This both verifies the periodic orbits and excludes additional ones.
Finally, if is fixed by , then for an integer vector . The eigenvalues of are and , neither zero. Hence its inverse exists and has rational entries by the adjugate matrix formula for an integer matrix. Therefore has rational coordinates. The derivative of the return map is , with eigenvalues and . Every periodic point is a hyperbolic saddle fixed point of a map and is unstable, although perturbations in its stable eigendirection contract.
With local path connectedness, the intended conclusion holds. Choose a base point and the standard covering map
The fundamental group of the circle is . Since the image of a finite group under a group homomorphism is finite and has no nontrivial finite subgroups,
is trivial. If is also locally path-connected, the lifting criterion for a covering space supplies a continuous map with , because . The homotopy
runs from to the constant function . This proves the claimed null-homotopy under that additional hypothesis, in particular for CW complexes and the topological graphs considered later in the paper.
For arbitrary path-connected spaces, the printed assertion is false. Here is an explicit Warsaw circle counterexample, including the obstruction that the usual lifting argument misses. In the Euclidean plane take
Join to by the polygonal arc passing successively through , and put with its subspace topology. The arc meets only at . The topologist's sine curve has two path components, but the added arc joins them, making path-connected.
Every loop in is contained in
for some . To justify the assertion, a path cannot reach along the oscillating tail: the intermediate value theorem for its -coordinate would force its -coordinate to attain both and arbitrarily close to the supposed arrival time, contradicting continuity. The only alternative route from the tail to uses and the joining arc. If a loop visited tail points with , a convergent subsequence of their parameter values would approach a time at which the loop lies in . On a sufficiently small parameter interval around that time its image avoids . That would give a forbidden path from into the tail without passing through . Thus those tail coordinates have a positive lower bound. The space is a finite tree, in fact a single arc, so every such loop contracts. Consequently
Now define a continuous map to be on , and to make one full turn on : for a parametrization from to , set . The pieces and are closed in , and the formulas agree at , so the pasting lemma for closed subspaces proves continuity.
There is no continuous lift . Any such lift is integer-valued on , so it is constant on each of the connected spaces . Since accumulates on , continuity forces those two constants to be the same. But along a lift of has the form , giving values at and differing by , a contradiction. Finally, if had a null-homotopy, the homotopy lifting theorem for a covering map, starting with a lift of the final constant function and reversing time, would produce a continuous lift of . This theorem needs no local path connectedness of the parameter space. Hence is not null-homotopic, although has finite, indeed trivial, fundamental group.
The native PDF explicitly assumes only path connectedness here. The missing local path connectedness cannot be inferred from the finiteness of the fundamental group.
True. Choose the irrational number , and partition the rational numbers into
No endpoint is rational, so these disjoint sets cover . Each is nonempty by the density of the rational numbers, and each is clopen in the subspace topology on .
Let two rational numbers be equivalent exactly when they belong to the same . The bijection
is well-defined. For every subset , the preimage of under the canonical projection of a quotient set is , which is open in . Thus every subset of is open: its quotient topology is the discrete topology. The usual subspace topology on the integers is also the discrete topology, because . Consequently is a homeomorphism.
Write and . The operands occupy the integer points of the square . The exact sum is representable precisely when
The upper boundary is , and the lower boundary is . Within the operand square, the closed band between these lines is representable. The triangle below the lower line has negative overflow, and the triangle above the upper line has positive overflow. The boundary lines themselves are included.
Consequently overflow occurs exactly when or . Negative overflow requires two negative operands; positive overflow requires two nonnegative operands. Same-sign operands alone are not sufficient: their exact sum must cross a range endpoint. Opposite-sign operands never overflow on addition. In terms of the stored wrapped result, addition overflows exactly when the operands have equal sign bits and the result has the opposite sign bit.
The illustration uses , so and , and marks every permissible operand pair. The general region follows from the same two inequalities for arbitrary .
An -bit two's complement word represents the integer
The leading bit has negative weight. Words beginning with zero encode the nonnegative values; words beginning with one encode the negative values. Equivalently, interpret the whole word as unsigned and subtract when its leading bit is one. For example, the four-bit words 0111, 1000, and 1111 encode , , and respectively. The range is asymmetric: the most negative value has no positive counterpart in the same number of bits.
For a nonzero representable magnitude, complementing all bits and adding one obtains its negative modulo . Fixed-width addition can therefore use the same low-order binary numeral system addition circuitry for signed and unsigned operands; interpreting the result as signed requires detecting integer overflow.
Use pattern matching to separate the empty list from a head and tail. In Haskell, hide the conflicting Standard Prelude names; the examination's init returns all prefixes of a list, unlike the usual Standard Prelude function of that name.
import Prelude hiding (map, length, init, tails, foldr, compare)

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

length :: Num n => [a] -> n
length [] = 0
length (_:xs) = 1 + length xs

copy :: (Eq n, Num n) => n -> a -> [a]
copy 0 xs = []
copy n xs = xs : copy (n-1) xs

combine :: [[a]] -> [[a]] -> [[a]]
combine [] _ = []
combine _ [] = []
combine (xs:xss) (ys:yss) = (xs ++ ys) : combine xss yss

init :: [a] -> [[a]]
init [] = [[]]
init (x:xs) = [] : map (x:) (init xs)

tails :: [a] -> [[a]]
tails [] = [[]]
tails (x:xs) = (x:xs) : tails xs
The map function preserves the input list shape while transforming each entry. length counts the cons cells. copy repeats the whole value xs, so for the specified use its second argument is a list and the result is a list of lists. Its inferred type is more general: the repeated value can have any data type. If one restricts the interface to lists, the corresponding type is (Eq n, Num n) => n -> [a] -> [[a]]. The numeric argument has the precondition that it is a nonnegative integer; the most general inferred numeric constraints do not guarantee termination on arbitrary values of their instances. An explicitly integral interface may instead use Integral n => n -> [a] -> [[a]].
combine performs list concatenation head by head and stops as soon as either outer list ends. For init, every nonempty prefix of a list starts with x and continues with a prefix of a list from xs; prepending [] supplies the shortest prefix of a list. For tails, the longest suffix of a list is the whole input, followed by all suffixes of a list of its tail. For example, init [1,2] = [[],[1],[1,2]] and tails [1,2] = [[1,2],[2],[]]. Thus both include the empty list, and
A string data type suffices for a name, an algebraic data type for the recorded sex, and a triple of integers for a date. Use a constructor for Person so that selectors are unambiguous in Haskell:
type Name = String
data Sex = Female | Male deriving (Eq, Show)
data Date = Date { day :: Int, month :: Int, year :: Int }
  deriving (Eq, Show)
data Person = Person { name :: Name, sex :: Sex, born :: Date }
  deriving (Eq, Show)
type BirthCertificate = (Person, Person, Person)
type Database = [BirthCertificate]
Dates have the precondition that their fields form a valid calendar date. This simple database representation assumes the triple of identifying fields distinguishes the recorded individuals; a production database would normally add a stable identifier to distinguish namesakes. The two constructors for Sex model the two recorded values used by this exercise. In mathematical notation,
For nonnegative integer x and positive integer y, initialize the quotient to zero and subtract one divisor at a time:
q := 0; r := x;
WHILE r >= y DO
  r := r-y;
  q := q+1
END
The loop invariant is , , , with x and y unchanged. It is true initially. A body execution changes to and keeps nonnegative because of the guard. The nonnegative integer loop variant strictly decreases by , so termination follows. At exit the guard supplies ; hence
There are exactly body executions. Under the unit-cost model, the time complexity including initialization and the final test is , which is for integer . This is a bound in the value of x, rather than in its encoded bit length.