[proofplan] We apply [Sylow's Third Theorem](/theorems/3251) to show that the number $n_q$ of Sylow $q$-subgroups is $1$, so the unique Sylow $q$-subgroup $Q$ is normal. When $p \nmid (q-1)$, the same argument forces $n_p = 1$, making both Sylow subgroups normal; since $P \cap Q = \{e\}$ and $|PQ| = pq$, the group is the direct product $P \times Q \cong \mathbb{Z}/pq\mathbb{Z}$. When $p \mid (q-1)$, the cyclic group is one possibility; the other arises from a non-constant homomorphism $\mathbb{Z}/p\mathbb{Z} \to \operatorname{Aut}(\mathbb{Z}/q\mathbb{Z})$, which exists and is unique up to the resulting isomorphism type, giving exactly one non-abelian group. [/proofplan]

[step:Show that $G$ has a unique Sylow $q$-subgroup]Write $|G| = pq$ with $p < q$ both prime. By [Sylow's First Theorem](/theorems/3249), $G$ has at least one Sylow $q$-subgroup, i.e., a subgroup of order $q$. Let $n_q$ denote the number of Sylow $q$-subgroups of $G$. By [Sylow's Third Theorem](/theorems/3251) applied with $|G| = q \cdot p$ (here $a = 1$ and $m = p$), the number $n_q$ satisfies \begin{align*} n_q \equiv 1 \pmod{q} \quad \text{and} \quad n_q \mid p. \end{align*} Since $p$ is prime, the divisibility condition gives $n_q \in \{1, p\}$. If $n_q = p$, then $n_q \equiv 1 \pmod{q}$ requires $p \equiv 1 \pmod{q}$, i.e., $q \mid (p - 1)$. But $p < q$ implies $0 < p - 1 < q$, so $q \nmid (p - 1)$. This is a contradiction, so $n_q = 1$. Let $Q$ denote the unique Sylow $q$-subgroup. Since conjugation permutes the set of Sylow $q$-subgroups and $Q$ is the only one, $gQg^{-1} = Q$ for all $g \in G$, so $Q \trianglelefteq G$.[/step]

[guided]We want to count the Sylow $q$-subgroups of $G$. A Sylow $q$-subgroup is a subgroup of order $q^1 = q$ (the largest power of $q$ dividing $|G| = pq$). [Sylow's First Theorem](/theorems/3249) guarantees at least one such subgroup exists. [Sylow's Third Theorem](/theorems/3251) constrains their number $n_q$: we need $n_q \equiv 1 \pmod{q}$ and $n_q \mid m$, where $|G| = q^a \cdot m$ with $q \nmid m$. Here $a = 1$ and $m = p$, so \begin{align*} n_q \equiv 1 \pmod{q} \quad \text{and} \quad n_q \mid p. \end{align*} Since $p$ is prime, the divisors of $p$ are $1$ and $p$, so $n_q \in \{1, p\}$. Could $n_q = p$? The congruence would require $p \equiv 1 \pmod{q}$, which means $q \mid (p - 1)$. But $p < q$ by hypothesis, so $p - 1 < q - 1 < q$, and since $p - 1 \geq 0$, the only way $q \mid (p-1)$ could hold is if $p - 1 = 0$, i.e., $p = 1$, which contradicts $p$ being prime. Therefore $n_q = 1$. Denote the unique Sylow $q$-subgroup by $Q$. Why is a unique Sylow subgroup automatically normal? For any $g \in G$, the conjugate $gQg^{-1}$ is also a Sylow $q$-subgroup (conjugation preserves subgroup order). Since $Q$ is the only Sylow $q$-subgroup, $gQg^{-1} = Q$ for every $g \in G$, which is exactly the definition of $Q \trianglelefteq G$.[/guided]

[step:Prove that $G$ is cyclic when $p \nmid (q - 1)$]By [Sylow's First Theorem](/theorems/3249), $G$ has a Sylow $p$-subgroup $P$ of order $p$. Let $n_p$ denote the number of Sylow $p$-subgroups. By [Sylow's Third Theorem](/theorems/3251) applied with $|G| = p \cdot q$ (here $a = 1$, $m = q$), \begin{align*} n_p \equiv 1 \pmod{p} \quad \text{and} \quad n_p \mid q. \end{align*} Since $q$ is prime, $n_p \in \{1, q\}$. If $n_p = q$, the congruence requires $q \equiv 1 \pmod{p}$, i.e., $p \mid (q - 1)$. By hypothesis $p \nmid (q - 1)$, so $n_p = 1$ and $P \trianglelefteq G$. Now both $P$ and $Q$ are normal in $G$. Since $|P| = p$ and $|Q| = q$ are distinct primes, [Lagrange's Theorem](/theorems/782) implies $|P \cap Q|$ divides $\gcd(p, q) = 1$, so $P \cap Q = \{e\}$. By [Lagrange's Theorem](/theorems/782), $|PQ| = |P| \cdot |Q| / |P \cap Q| = pq = |G|$, so $G = PQ$. Since $P$ and $Q$ are both normal with $P \cap Q = \{e\}$ and their product is $G$, the map \begin{align*} \mu: P \times Q &\to G \\ (a, b) &\mapsto ab \end{align*} is a group isomorphism. (Well-definedness and the homomorphism property follow from normality: for $a \in P$, $b \in Q$, the commutator $aba^{-1}b^{-1} = (aba^{-1})b^{-1} \in Q$ since $Q \trianglelefteq G$, and $a(ba^{-1}b^{-1}) \in P$ since $P \trianglelefteq G$; so $aba^{-1}b^{-1} \in P \cap Q = \{e\}$, giving $ab = ba$.) Since $P \cong \mathbb{Z}/p\mathbb{Z}$ and $Q \cong \mathbb{Z}/q\mathbb{Z}$ (every group of prime order is cyclic), and $\gcd(p, q) = 1$, the [Chinese Remainder Theorem](/theorems/734) gives \begin{align*} G \cong \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z} \cong \mathbb{Z}/pq\mathbb{Z}. \end{align*}[/step]

[guided]We now apply [Sylow's Third Theorem](/theorems/3251) to the prime $p$. Writing $|G| = p \cdot q$ with $p \nmid q$ (since $p$ and $q$ are distinct primes), we get $a = 1$ and $m = q$. The theorem gives \begin{align*} n_p \equiv 1 \pmod{p} \quad \text{and} \quad n_p \mid q. \end{align*} Since $q$ is prime, $n_p \in \{1, q\}$. If $n_p = q$, then $q \equiv 1 \pmod{p}$, meaning $p \mid (q - 1)$. But we are assuming $p \nmid (q - 1)$, so this case is excluded. Therefore $n_p = 1$, and the unique Sylow $p$-subgroup $P$ is normal in $G$ (by the same uniqueness-implies-normality argument as before). We now have two normal subgroups $P \trianglelefteq G$ and $Q \trianglelefteq G$ with $|P| = p$ and $|Q| = q$. We claim $G \cong P \times Q$. To verify this, we need three things: **Trivial intersection.** Since $P \cap Q \le P$ and $P \cap Q \le Q$, [Lagrange's Theorem](/theorems/782) gives $|P \cap Q| \mid p$ and $|P \cap Q| \mid q$. Because $p \neq q$ are both prime, $\gcd(p, q) = 1$, forcing $|P \cap Q| = 1$, i.e., $P \cap Q = \{e\}$. **Product equals $G$.** The product set $PQ = \{ab : a \in P, b \in Q\}$ is a subgroup of $G$ (since $Q \trianglelefteq G$, the product $PQ$ is closed under multiplication). Its size is $|PQ| = |P| \cdot |Q| / |P \cap Q| = pq / 1 = pq = |G|$, so $PQ = G$. **Elements of $P$ and $Q$ commute.** For any $a \in P$ and $b \in Q$, consider the commutator $[a, b] = aba^{-1}b^{-1}$. Since $Q \trianglelefteq G$, the element $aba^{-1} \in Q$, so $aba^{-1}b^{-1} \in Q$. Since $P \trianglelefteq G$, the element $ba^{-1}b^{-1} \in P$, so $a(ba^{-1}b^{-1}) \in P$, meaning $aba^{-1}b^{-1} \in P$. Therefore $[a, b] \in P \cap Q = \{e\}$, so $ab = ba$. With these three properties, the multiplication map $\mu: P \times Q \to G$, $(a, b) \mapsto ab$, is a group isomorphism. Finally, $P$ and $Q$ have prime orders $p$ and $q$ respectively, so each is cyclic: $P \cong \mathbb{Z}/p\mathbb{Z}$ and $Q \cong \mathbb{Z}/q\mathbb{Z}$. Since $\gcd(p, q) = 1$, the [Chinese Remainder Theorem](/theorems/734) gives $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z} \cong \mathbb{Z}/pq\mathbb{Z}$, and therefore $G \cong \mathbb{Z}/pq\mathbb{Z}$.[/guided]

[step:Classify the two isomorphism types when $p \mid (q - 1)$]Assume $p \mid (q - 1)$. From the previous step, $Q \trianglelefteq G$ always holds. Let $P \le G$ be a Sylow $p$-subgroup. Since $P \cap Q = \{e\}$ (as before, $|P \cap Q|$ divides $\gcd(p,q) = 1$) and $|PQ| = pq = |G|$, we have $G = PQ$. Because $Q \trianglelefteq G$, the group $G$ is a semidirect product $G \cong Q \rtimes_\varphi P$ for some homomorphism \begin{align*} \varphi: P &\to \operatorname{Aut}(Q). \end{align*} Since $|P| = p$ and $|Q| = q$ are prime, $P \cong \mathbb{Z}/p\mathbb{Z}$ and $Q \cong \mathbb{Z}/q\mathbb{Z}$. The automorphism group $\operatorname{Aut}(\mathbb{Z}/q\mathbb{Z}) \cong (\mathbb{Z}/q\mathbb{Z})^\times$ is cyclic of order $q - 1$. **Case 1: $\varphi$ is the constant homomorphism** (sending every element of $P$ to $\operatorname{id}_Q$). Then the semidirect product is a direct product: $G \cong Q \times P \cong \mathbb{Z}/q\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z} \cong \mathbb{Z}/pq\mathbb{Z}$. **Case 2: $\varphi$ is non-constant.** Since $P \cong \mathbb{Z}/p\mathbb{Z}$, a homomorphism $\varphi: \mathbb{Z}/p\mathbb{Z} \to (\mathbb{Z}/q\mathbb{Z})^\times$ is determined by the image of a generator. The image must have order dividing $p$ in $(\mathbb{Z}/q\mathbb{Z})^\times$. Since $p \mid (q - 1) = |(\mathbb{Z}/q\mathbb{Z})^\times|$ and $(\mathbb{Z}/q\mathbb{Z})^\times$ is cyclic, there is a unique subgroup of order $p$ in $(\mathbb{Z}/q\mathbb{Z})^\times$, which contains exactly $p - 1$ elements of order $p$. Any two non-constant homomorphisms $\varphi, \varphi': \mathbb{Z}/p\mathbb{Z} \to (\mathbb{Z}/q\mathbb{Z})^\times$ have images in this same cyclic subgroup of order $p$. We claim that the resulting semidirect products are isomorphic. [claim:Different non-constant homomorphisms yield isomorphic semidirect products] Let $\varphi, \varphi': \mathbb{Z}/p\mathbb{Z} \to \operatorname{Aut}(\mathbb{Z}/q\mathbb{Z})$ be two non-constant homomorphisms. Then $\mathbb{Z}/q\mathbb{Z} \rtimes_\varphi \mathbb{Z}/p\mathbb{Z} \cong \mathbb{Z}/q\mathbb{Z} \rtimes_{\varphi'} \mathbb{Z}/p\mathbb{Z}$. [/claim] [proof] Let $t$ be a generator of $\mathbb{Z}/p\mathbb{Z}$ and let $\varphi(t) = \alpha \in \operatorname{Aut}(\mathbb{Z}/q\mathbb{Z})$, where $\alpha$ has order $p$. Since $\varphi'$ is also non-constant, $\varphi'(t) = \alpha^k$ for some $1 \le k \le p - 1$ (as both images lie in the unique cyclic subgroup of order $p$ in $\operatorname{Aut}(\mathbb{Z}/q\mathbb{Z})$, which is generated by $\alpha$). Since $\gcd(k, p) = 1$ (otherwise $\alpha^k$ would have order less than $p$, contradicting $\varphi'$ being non-constant), $k$ is invertible modulo $p$. The map $t \mapsto t^k$ is an automorphism of $\mathbb{Z}/p\mathbb{Z}$, and it satisfies $\varphi'(t) = \varphi(t^k)$, so $\varphi' = \varphi \circ \psi$ where $\psi: \mathbb{Z}/p\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z}$ is the automorphism $s \mapsto s^k$. The map \begin{align*} \Theta: \mathbb{Z}/q\mathbb{Z} \rtimes_{\varphi'} \mathbb{Z}/p\mathbb{Z} &\to \mathbb{Z}/q\mathbb{Z} \rtimes_\varphi \mathbb{Z}/p\mathbb{Z} \\ (a, s) &\mapsto (a, \psi(s)) = (a, s^k) \end{align*} is a group isomorphism. To verify the homomorphism property: in $\mathbb{Z}/q\mathbb{Z} \rtimes_{\varphi'} \mathbb{Z}/p\mathbb{Z}$, the multiplication rule is $(a, s)(b, s') = (a + \varphi'(s)(b),\, s + s')$. Applying $\Theta$: \begin{align*} \Theta((a, s)(b, s')) = (a + \varphi'(s)(b),\, (s+s')^k) = (a + \varphi(s^k)(b),\, s^k + {s'}^k). \end{align*} On the other hand, $\Theta(a,s) \cdot \Theta(b,s') = (a, s^k)(b, {s'}^k) = (a + \varphi(s^k)(b),\, s^k + {s'}^k)$. These coincide. Injectivity follows from $\psi$ being an automorphism, and surjectivity from $\psi$ being surjective. [/proof] Therefore there are exactly two isomorphism types: the cyclic group (from the constant homomorphism $\varphi \equiv \operatorname{id}$) and one non-abelian group (from any non-constant homomorphism). The non-abelian group is not cyclic because it is non-abelian, so these two types are distinct.[/step]

[guided]When $p \mid (q - 1)$, the Sylow analysis from the first step still gives $n_q = 1$, so $Q \trianglelefteq G$. However, $n_p$ is no longer forced to be $1$: we have $n_p \in \{1, q\}$ and $n_p = q$ is now consistent with the congruence $n_p \equiv 1 \pmod{p}$, since $p \mid (q - 1)$ means $q \equiv 1 \pmod{p}$. So we cannot conclude $P \trianglelefteq G$ from Sylow alone. **Expressing $G$ as a semidirect product.** Regardless of whether $P$ is normal, we can still describe $G$ structurally. Fix a Sylow $p$-subgroup $P \le G$. Since $Q \trianglelefteq G$ and $P \cap Q = \{e\}$ (because $|P \cap Q|$ divides $\gcd(p, q) = 1$ by [Lagrange's Theorem](/theorems/782)), and $|PQ| = |P| \cdot |Q| / |P \cap Q| = pq = |G|$, the group satisfies $G = PQ$ with $Q \trianglelefteq G$ and $P \cap Q = \{e\}$. This is precisely the condition for $G$ to be the internal semidirect product $G = Q \rtimes_\varphi P$, where $\varphi: P \to \operatorname{Aut}(Q)$ is the conjugation action: $\varphi(a)(b) = aba^{-1}$ for $a \in P$, $b \in Q$. (The action is well-defined because $Q \trianglelefteq G$ guarantees $aba^{-1} \in Q$.) **Classifying the homomorphisms $\varphi: \mathbb{Z}/p\mathbb{Z} \to \operatorname{Aut}(\mathbb{Z}/q\mathbb{Z})$.** Since $|P| = p$ and $|Q| = q$ are prime, both are cyclic: $P \cong \mathbb{Z}/p\mathbb{Z}$ and $Q \cong \mathbb{Z}/q\mathbb{Z}$. The automorphism group $\operatorname{Aut}(\mathbb{Z}/q\mathbb{Z}) \cong (\mathbb{Z}/q\mathbb{Z})^\times$ is cyclic of order $q - 1$ (each automorphism is multiplication by a unit mod $q$). A group homomorphism from $\mathbb{Z}/p\mathbb{Z}$ into any group is entirely determined by the image of a generator $t \in \mathbb{Z}/p\mathbb{Z}$, and that image must have order dividing $p$. So we need elements of order dividing $p$ in $(\mathbb{Z}/q\mathbb{Z})^\times$. There are two types of such elements: the identity (order $1$), and elements of order exactly $p$. Sending $t$ to the identity gives the constant homomorphism $\varphi \equiv \operatorname{id}$; this yields the direct product $G \cong \mathbb{Z}/q\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z} \cong \mathbb{Z}/pq\mathbb{Z}$. Since $p \mid (q - 1)$ and $(\mathbb{Z}/q\mathbb{Z})^\times$ is cyclic of order $q - 1$, there exists a unique subgroup of order $p$ in $(\mathbb{Z}/q\mathbb{Z})^\times$ (a cyclic group has exactly one subgroup of each order dividing its order). This subgroup has $p - 1$ generators, each of order $p$, giving exactly $p - 1$ non-constant homomorphisms $\varphi: \mathbb{Z}/p\mathbb{Z} \to (\mathbb{Z}/q\mathbb{Z})^\times$. **Do different non-constant homomorphisms yield non-isomorphic groups?** No — all non-constant homomorphisms produce isomorphic semidirect products. Here is the explicit verification. Let $t$ be a generator of $\mathbb{Z}/p\mathbb{Z}$. Let $\varphi, \varphi': \mathbb{Z}/p\mathbb{Z} \to \operatorname{Aut}(\mathbb{Z}/q\mathbb{Z})$ be two non-constant homomorphisms. Write $\varphi(t) = \alpha$ where $\alpha \in \operatorname{Aut}(\mathbb{Z}/q\mathbb{Z})$ has order $p$. Since $\varphi'$ is also non-constant, $\varphi'(t)$ lies in the unique subgroup of order $p$ in $\operatorname{Aut}(\mathbb{Z}/q\mathbb{Z})$, which is generated by $\alpha$. Thus $\varphi'(t) = \alpha^k$ for some $1 \le k \le p - 1$. Since $\gcd(k, p) = 1$ (if $p \mid k$ then $\alpha^k = \operatorname{id}$, contradicting $\varphi'$ being non-constant), $k$ is invertible modulo $p$. Define $\psi: \mathbb{Z}/p\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z}$ by $\psi(s) = s^k$ (i.e., multiplication by $k$ in $\mathbb{Z}/p\mathbb{Z}$). Since $\gcd(k, p) = 1$, $\psi$ is an automorphism of $\mathbb{Z}/p\mathbb{Z}$. Moreover, $\varphi'(t) = \alpha^k = \varphi(t^k) = \varphi(\psi(t))$, so $\varphi' = \varphi \circ \psi$. Now define \begin{align*} \Theta: \mathbb{Z}/q\mathbb{Z} \rtimes_{\varphi'} \mathbb{Z}/p\mathbb{Z} &\to \mathbb{Z}/q\mathbb{Z} \rtimes_\varphi \mathbb{Z}/p\mathbb{Z} \\ (a, s) &\mapsto (a,\, \psi(s)) = (a,\, s^k). \end{align*} We verify $\Theta$ is a group homomorphism. The multiplication rule in $\mathbb{Z}/q\mathbb{Z} \rtimes_{\varphi'} \mathbb{Z}/p\mathbb{Z}$ is $(a, s)(b, s') = (a + \varphi'(s)(b),\, s + s')$. Applying $\Theta$: \begin{align*} \Theta\bigl((a, s)(b, s')\bigr) = \Theta\bigl(a + \varphi'(s)(b),\, s + s'\bigr) = \bigl(a + \varphi'(s)(b),\, (s + s')^k\bigr). \end{align*} Since $\psi$ is a group homomorphism (i.e., $(s + s')^k = s^k + {s'}^k$ in $\mathbb{Z}/p\mathbb{Z}$) and $\varphi'(s) = \varphi(\psi(s)) = \varphi(s^k)$, this equals $(a + \varphi(s^k)(b),\, s^k + {s'}^k)$. On the other hand: \begin{align*} \Theta(a, s) \cdot \Theta(b, s') = (a, s^k)(b, {s'}^k) = (a + \varphi(s^k)(b),\, s^k + {s'}^k). \end{align*} These are equal, so $\Theta$ is a homomorphism. Since $\psi$ is an automorphism, the map $(a, s) \mapsto (a, s^k)$ is both injective and surjective, so $\Theta$ is an isomorphism. Therefore $\mathbb{Z}/q\mathbb{Z} \rtimes_{\varphi'} \mathbb{Z}/p\mathbb{Z} \cong \mathbb{Z}/q\mathbb{Z} \rtimes_\varphi \mathbb{Z}/p\mathbb{Z}$. **Conclusion.** There are exactly two isomorphism classes of groups of order $pq$ when $p \mid (q - 1)$: - The cyclic group $\mathbb{Z}/pq\mathbb{Z}$, arising when $\varphi$ is the constant homomorphism (sending every element to $\operatorname{id}$), in which case $G$ is abelian and $n_p = 1$. - The unique non-abelian group $\mathbb{Z}/q\mathbb{Z} \rtimes_\varphi \mathbb{Z}/p\mathbb{Z}$, arising when $\varphi$ is any non-constant homomorphism; all such choices yield isomorphic groups, and $n_p = q$ in this case. These two classes are distinct because the non-abelian group is not abelian while $\mathbb{Z}/pq\mathbb{Z}$ is abelian (in particular, the non-abelian group is not cyclic).[/guided]