Let $A$ be the adjacency matrix of a graph, $J$ the all-ones matrix and $1$ the all-ones vector. Counting two-step walks givesBecause $b\ge 1$, any two nonadjacent vertices have a common neighbour, so the graph is connected. The eigenvalue $k$ is simple: for a real eigenvector at $k$, a maximal entry and the averaging equation force its neighbours, and then every vertex, to have the same value. Since $A$ is real symmetric, its other eigenvectors lie in $1^{\perp }$, where $J$ vanishes. Their eigenvalues are thereforeHere $d>0$ for the present incomplete connected graph. Indeed $k\ge b$; if $d=0$, then $k=b=a$, which conflicts with $a\le k-1$ for an edge. If $r,s$ have multiplicities $m_r,m_s$, dimension and zero trace give $m_r+m_s=n-1$ and $k+m_{r}r+m_{s}s=0$. ThusThese are dimensions of eigenspaces, hence integers. A multiplicity may be zero; that does not affect the conclusion.

A strongly regular graph with parameters $(k,a,b)$ is a simple graph in which each vertex has degree $k$, adjacent vertices have exactly $a$ common neighbours, and distinct nonadjacent vertices have exactly $b$ common neighbours. Its order $n$ is often included separately as a fourth parameter.

Let $j:B\to \mathbb{N}$ be an injection witnessing that $B$ is a countable set. The composition $j\circ f:A\to \mathbb{N}$ is an injection, so $A$ is a countable set. This proof includes finite and empty sets.

Write both nonnegative integers $n,k$ in base-p expansions, padding with zero digits to a common length $L$. By the preceding polynomial identity,Expanding the last product with the binomial theorem, each term is obtained by choosing an integer $j_i$ with $0\le j_i\le n_i<p$. Its exponent is ${\sum }_i{j}_i{p}^i$ and its coefficient is ${\prod }_i\left(\genfrac{}{}{0ex}{}{n_i}{j_i}\right)$. Uniqueness of base-p expansions says that the only way this exponent can equal $k$ is to choose $j_i=k_i$ for every $i$.

If some $k_i>n_i$, no such term exists and the coefficient is zero. Otherwise its coefficient is precisely the product below. Comparing the coefficient of $x^k$ proves Lucas theorem:with the convention $\left(\genfrac{}{}{0ex}{}{a}{b}\right)=0$ for $b>a$. This also covers $k>n$, and padding either expansion by further zero digits multiplies the product only by $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$.

For $1\le j\le p-1$, the identity for binomial coefficientsshows that $p$ divides $j\left(\genfrac{}{}{0ex}{}{p}{j}\right)$. Since $p$ is a prime number and $j$ is not divisible by $p$, cancellation modulo $p$ givesThe binomial theorem consequently gives $(1+x{)}^p\equiv 1+x^p$ as a coefficientwise polynomial modular congruence. Apply the same identity with $x$ replaced by $x^{p^r}$ and use mathematical induction to obtainThis is an iteration of the Frobenius endomorphism in characteristic $p$. Comparing the intermediate coefficients gives the prime-power binomial divisibility result

Suppose two base-p expansions represent the same nonnegative integer. Pad the shorter one by trailing zero digits so that both have the same length. Reducing modulo $p$ shows that their first digits satisfy $k_0\equiv k_0^{\prime }(\mathrm{mod}p)$. Since both digits lie between $0$ and $p-1$, they are equal as integers.

Subtract that common digit and divide by $p$. The remaining equality is an equality of two base-p expansions with one fewer digit. Repeating this argument shows that every pair of corresponding digits agrees. Equivalently, repeated Euclidean division recovers the digits as remainders. The digits are unique up to padding by zeroes. The finite nonnegative-digit representation presupposes $k\ge 0$; a negative integer has no such expansion.

Reflexivity follows by taking the two exponents equal to $1$, and symmetry is built into the two divisibility conditions. For transitivity, suppose $m\mid n^a$, $n\mid m^b$, $n\mid {\ell }^c$ and $\ell \mid n^d$. Then $m\mid {\ell }^{ac}$ and $\ell \mid m^{bd}$, with positive exponents. Thus the relation is an equivalence relation.

Its equivalence classes have a useful description by prime factorization. Let $S(n)$ be the finite set of prime factors of $n$, with $S(1)=\varnothing$. If $m\mid n^a$, every prime factor of $m$ divides $n$; the reverse divisibility gives $S(n)\subseteq S(m)$. Conversely, if $S(m)=S(n)$, write $m={\prod }_{p\in S}{p}^{{\alpha }_p}$ and $n={\prod }_{p\in S}{p}^{{\beta }_p}$, with all exponents positive. Choosing $a\ge {\max }_p\lceil {\alpha }_p/{\beta }_p\rceil$ and $b\ge {\max }_p\lceil {\beta }_p/{\alpha }_p\rceil$ gives the required divisibilities. The empty case is exactly $m=n=1$.

Therefore the prime-support equivalence relation iswhere the radical of an integer is the product of its distinct prime factors. The class with empty support is $\{1\}$. For every nonempty finite support $S$, all positive exponent choices give one class, and varying just one exponent produces infinitely many different integers in it.

There are infinitely many classes because each prime number gives a different singleton support. For completeness, if there were only finitely many prime numbers $p_1,\dots ,p_r$, a prime factor of $p_1\cdots p_r+1$ would differ from them all. There are infinitely many classes; the unique finite class is $\{1\}$.

For an equivalence relation $\sim$ on $X$, the equivalence class of $x\in X$ is $[x]=\{y\in X:y\sim x\}$. A set partition is a family of nonempty, pairwise disjoint subsets whose union is $X$.

Reflexivity ensures $x\in [x]$, so every equivalence class is nonempty and every element belongs to one. If $[x]\cap [y]$ contains $z$, then $z\sim x$ and $z\sim y$; symmetry and transitivity give $x\sim y$. If $w\in [x]$, transitivity gives $w\sim y$, so $w\in [y]$; interchanging $x,y$ gives the reverse inclusion. Thus intersecting equivalence classes are equal.

Taking the collection of distinct equivalence classes therefore produces a set partition of $X$. Every element lies in exactly one class. If $X$ is empty, the empty family is its set partition.

Write the composite number as $n=ab$, with $2\le a\le b<n$. If $a<b$, both $a$ and $b$ occur as distinct factors of the factorial $(n-1)!$, so their product $n$ divides that factorial.

If $a=b$, then $n=a^2$ and $n>4$ implies $a\ge 3$. Both $a$ and $2a$ are distinct factors in $(n-1)!$, because $2a\le a^2-1$. Their product is $2n$, so again $n$ divides the factorial. HenceThe exception $n=4$ matters: its factorial $3!=6$ is not divisible by $4$. This argument handles perfect squares without incorrectly counting the same factor twice.

Subtracting twice the first linear congruence from the second gives $5x\equiv 1(\mathrm{mod}53)$. Since $5\cdot 32=3\cdot 53+1$, the modular inverse of $5$ modulo $53$ is $32$. Thus $x\equiv 32(\mathrm{mod}53)$. Substitution in the first linear congruence then gives $2y\equiv 23(\mathrm{mod}53)$, whence $y\equiv 38(\mathrm{mod}53)$. All integer solutions areThe two free integers are independent. Conversely, these values give $6x+2y\equiv 268\equiv 3$ and $17x+4y\equiv 696\equiv 7(\mathrm{mod}53)$, so no additional restriction is needed.

For the modular Heisenberg group, the three independent entries each have $p$ choices, soThe multiplication and commutation calculations work over the finite field ${\mathbb{F}}_p$ exactly as over $\mathbb{R}$. Taking $x^{\prime }=1,z^{\prime }=0$ and $x^{\prime }=0,z^{\prime }=1$ shows thatLet $c=M(0,1,0)$. Its powers exhaust the centre and $c$ has order $p$, giving the group presentationLet $a=M(1,0,0)$ and $b=M(0,0,1)$. Their images $\bar{a},\bar{b}$ in the quotient group translate the $x,z$ entries independently. They commute modulo the centre, have order $p$, and generate $p^2$ distinct pairs. ThereforeFor context, $ab{a}^{-1}{b}^{-1}=c$, with $c$ central. All conclusions above include $p=2$; one must not infer that every nonidentity element of $H_2$ has order two, since $(ab{)}^2=c$.

Write the Heisenberg group element as $M(x,y,z)$. Matrix multiplication and inversion giveAll matrices have determinant one. They contain $M(0,0,0)=I$, are closed under multiplication and inverses, and inherit associativity from matrix multiplication; hence they form a subgroup of $G{L}_3(\mathbb{R})$.

Two such matrices commute precisely when $x{z}^{\prime }=x^{\prime }z$. Requiring this for every $x^{\prime },z^{\prime }$ forces $x=z=0$. ConsequentlyThe map $\pi (M(x,y,z))=(x,z)$ is a surjective group homomorphism to the additive group ${\mathbb{R}}^2$, with kernel of a group homomorphism $Z(H)$. Equivalently, it gives the explicit quotient group isomorphismIt is well-defined because multiplying by a central element changes only $y$. It is injective because equal $(x,z)$ imply that the quotient of the two matrices is central, and surjectivity follows by taking $y=0$. This also proves the needed instance of the first isomorphism theorem directly.

The identity belongs to the center of a group. If $z,w$ commute with every $g$, then $zw$ does too; rearranging $gz=zg$ also shows that $z^{-1}$ commutes with $g$. Hence $Z(G)$ is a subgroup. Moreover $gz{g}^{-1}=z$ for $z\in Z(G)$, so it is a normal subgroup.

Suppose $|G|=p^n>1$. The conjugation action partitions $G$ into conjugacy classes. The orbit-stabilizer theorem gives class size $[G:C_G(x)]$, where $C_G(x)$ is the centralizer of $x$. By Lagrange's theorem, this size is a power of $p$; it is one exactly when $x$ is central. Thus the class equation has the formIt follows that $p\mid |Z(G)|$. Since the identity is central, $|Z(G)|\ge 1$, and thereforeThis is the nontrivial-centre property of a finite p-group.

Lagrange's theorem says that, for a finite group $G$ and subgroup $H$,Here $[G:H]$ is the number of left cosets. Every $g\in G$ lies in $gH$. If $gH$ and $g^{\prime }H$ meet, write $gh=g^{\prime }{h}^{\prime }$; then $g^{\prime }=gh(h^{\prime }{)}^{-1}$, so $g^{\prime }H=gH$. Hence the left cosets partition $G$. The bijection $h\mapsto gh$ makes each coset have $|H|$ elements. Adding their cardinalities proves Lagrange's theorem.

False. Any supposed kernel of a group homomorphism of order two would have a nonidentity central element by the introductory proof. Every element of order two in $S_3$ is a transposition, and none is central: conjugating $(ij)$ by a suitable three-cycle gives a different transposition. Thus the center of a group for $S_3$ is trivial, and such a kernel is impossible. This argument does not assume that an arbitrary order-two subgroup is normal.