Return to Question

For small values of $n$ and $(a, n) = 1$ it is sometimes possible to give an elementary proof that there are infinitely many primes congruent to $a \bmod n$ along the lines of Euclid's classic proof of the infinitude of the primes. The idea is to find a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $a \bmod n$ or $1 \bmod n$, and such that the first case occurs infinitely many times; then one proves, just as Euclid did, that the integer values of $p$ are divisible by infinitely many primes, and then one contrives to avoid the residue $1 \bmod n$ (if $a \neq 1$; if $a = 1$ then we take $p(t) = \Phi_n(t)$.) Results of Schur and Murty (see this paper of Keith Conrad) then imply that such a polynomial $p$ exists if and only if $a^2 \equiv 1 \bmod n$.

Say that a subset $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ has property E if there exists a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $s \bmod n$ or $1 \bmod n$ for some $s \in S$, and such that the first case occurs infinitely many times. Then we know that any $S$ containing an element squaring to $1$ has property E.

However, there exist subsets $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ not containing such an element with property E. For example, let $G$ be a proper subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$, let $a \not \in G$, and consider

$$p(t) = nt + a.$$

Any prime divisor of $n + a$ is relatively prime to $a$, and at least one of these prime divisors must have residue $\bmod n$ not in $G$. If $p_1, ... p_k$ are finitely many such primes, then $p(p_1 ... p_k) \equiv a \bmod n$ and hence must have a prime factor with the same property which moreover is relatively prime to each $p_i$. It follows that $S = (\mathbb{Z}/n\mathbb{Z})^{\ast} - G$ has property E, and if $n$ does not divide $24$, then taking $G$ to be the subgroup of square roots of $1$ gives the desired example.

Question: What subsets $S$ of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ have property E and are minimal under inclusion? Are they closed under non-empty intersection?

(If this question is somehow answered in Conrad's paper, my apologies; the material is somewhat beyond me.)

For small values of $n$ and $(a, n) = 1$ it is sometimes possible to give an elementary proof that there are infinitely many primes congruent to $a \bmod n$ along the lines of Euclid's classic proof of the infinitude of the primes. The idea is to find a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $a \bmod n$ or $1 \bmod n$, and such that the first case occurs infinitely many times; then one proves, just as Euclid did, that the integer values of $p$ are divisible by infinitely many primes, and then one contrives to avoid the residue $1 \bmod n$ (if $a \neq 1$; if $a = 1$ then we take $p(t) = \Phi_n(t)$.) Results of Schur and Murty (see Keith Conrad, "Euclidean proofs of Dirichlet's theorem") then imply that such a polynomial $p$ exists if and only if $a^2 \equiv 1 \bmod n$.

Say that a subset $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ has property E if there exists a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $s \bmod n$ or $1 \bmod n$ for some $s \in S$, and such that the first case occurs infinitely many times. Then we know that any $S$ containing an element squaring to $1$ has property E.

However, there exist subsets $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ not containing such an element with property E. For example, let $G$ be a proper subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$, let $a \notin G$, and consider

$$P(t) = nt + a.$$

Any prime divisor of $n + a$ is relatively prime to $a$, and at least one of these prime divisors must have residue $\bmod n$ not in $G$. If $p_1, \dotsc p_k$ are finitely many such primes, then $P(p_1 \dotsm p_k) \equiv a \bmod n$ and hence must have a prime factor with the same property which moreover is relatively prime to each $p_i$. It follows that $S = (\mathbb{Z}/n\mathbb{Z})^{\ast} - G$ has property E, and if $n$ does not divide $24$, then taking $G$ to be the subgroup of square roots of $1$ gives the desired example.

Question: What subsets $S$ of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ have property E and are minimal under inclusion? Are they closed under non-empty intersection?

(If this question is somehow answered in Conrad's paper, my apologies; the material is somewhat beyond me.)

For small values of $n$ and $(a, n) = 1$ it is sometimes possible to give an elementary proof that there are infinitely many primes congruent to $a \bmod n$ along the lines of Euclid's classic proof of the infinitude of the primes. The idea is to find a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $a \bmod n$ or $1 \bmod n$, and such that the first case occurs infinitely many times; then one proves, just as Euclid did, that the integer values of $p$ are divisible by infinitely many primes, and then one contrives to avoid the residue $1 \bmod n$ (if $a \neq 1$; if $a = 1$ then we take $p(t) = \Phi_n(t)$.) Results of Schur and Murty (see this paper of Keith Conrad) then imply that such a polynomial $p$ exists if and only if $a^2 \equiv 1 \bmod n$.

Say that a subset $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ has property E if there exists a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $s \bmod n$ or $1 \bmod n$ for some $s \in S$, and such that the first case occurs infinitely many times. Then we know that any $S$ containing an element squaring to $1$ has property E.

However, there exist subsets $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ not containing such an element with property E. For example, let $G$ be a proper subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$, let $a \not \in G$, and consider

$$p(t) = nt + a.$$

Any prime divisor of $n + a$ is relatively prime to $a$, and at least one of these prime divisors must have residue $\bmod n$ not in $G$. If $p_1, ... p_k$ are finitely many such primes, then $p(p_1 ... p_k) \equiv a \bmod n$ and hence must have a prime factor with the same property which moreover is relatively prime to each $p_i$. It follows that $S = (\mathbb{Z}/n\mathbb{Z})^{\ast} - G$ has property E, and if $n$ does not divide $24$, then taking $G$ to be the subgroup of square roots of $1$ gives the desired example.

Question: What subsets $S$ of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ have property E and are minimal under inclusion? Are they closed under non-empty intersection?

(If this question is somehow answered in Conrad's paper, my apologies; the material is somewhat beyond me.)

For small values of $n$ and $(a, n) = 1$ it is sometimes possible to give an elementary proof that there are infinitely many primes congruent to $a \bmod n$ along the lines of Euclid's classic proof of the infinitude of the primes. The idea is to find a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $a \bmod n$ or $1 \bmod n$, and such that the first case occurs infinitely many times; then one proves, just as Euclid did, that the integer values of $p$ are divisible by infinitely many primes, and then one contrives to avoid the residue $1 \bmod n$ (if $a \neq 1$; if $a = 1$ then we take $p(t) = \Phi_n(t)$.) Results of Schur and Murty (see this paper of Keith Conrad) then imply that such a polynomial $p$ exists if and only if $a^2 \equiv 1 \bmod n$.

Say that a subset $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ has property E if there exists a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $s \bmod n$ or $1 \bmod n$ for some $s \in S$, and such that the first case occurs infinitely many times. Then we know that any $S$ containing an element squaring to $1$ has property E.

However, there exist subsets $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ not containing such an element with property E. For example, let $G$ be a proper subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$, let $a \not \in G$, and consider

$$p(t) = nt + a.$$

Any prime divisor of $n + a$ is relatively prime to $a$, and at least one of these prime divisors must have residue $\bmod n$ not in $G$. If $p_1, ... p_k$ are finitely many such primes, then $p(p_1 ... p_k) \equiv a \bmod n$ and hence must have a prime factor with the same property which moreover is relatively prime to each $p_i$. It follows that $S = (\mathbb{Z}/n\mathbb{Z})^{\ast} - G$ has property E, and if $n$ does not divide $24$, then taking $G$ to be the subgroup of square roots of $1$ gives the desired example.

Question: What subsets $S$ of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ have property E and are minimal under inclusion? Are they closed under non-empty intersection?

(If this question is somehow answered in Conrad's paper, my apologies; the material is somewhat beyond me.)

For small values of $n$ and $(a, n) = 1$ it is sometimes possible to give an elementary proof that there are infinitely many primes congruent to $a \bmod n$ along the lines of Euclid's classic proof of the infinitude of the primes. The idea is to find a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $a \bmod n$ or $1 \bmod n$, and such that the first case occurs infinitely many times; then one proves, just as Euclid did, that the integer values of $p$ are divisible by infinitely many primes, and then one contrives to avoid the residue $1 \bmod n$ (if $a \neq 1$; if $a = 1$ then we take $p(t) = \Phi_n(t)$.) Results of Schur and Murty (see this paper of Keith Conrad) then imply that such a polynomial $p$ exists if and only if $a^2 \equiv 1 \bmod n$.

Say that a subset $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ has property E if there exists a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $s \bmod n$ or $1 \bmod n$ for some $s \in S$, and such that the first case occurs infinitely many times. Then we know that any $S$ containing an element squaring to $1$ has property E.

However, there exist subsets $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ not containing such an element with property E. For example, let $G$ be a proper subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$, let $a \not \in G$, and consider

$$p(t) = nt + a.$$

Any prime divisor of $n + a$ is relatively prime to $a$, and at least one of these prime divisors must have residue $\bmod n$ not in $G$. If $p_1, ... p_k$ are finitely many such primes, then $p(p_1 ... p_k) \equiv a \bmod n$ and hence must have a prime factor with the same property which moreover is relatively prime to each $p_i$. It follows that $S = (\mathbb{Z}/n\mathbb{Z})^{\ast} - G$ has property E, and if $\phi(n)$ is not a power of $2$, then taking $G$ to be the subgroup generated by the square roots of $1$ gives the desired example.

Question: What subsets $S$ of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ not containing square roots of $1$ have property E?

(If this question is somehow answered in Conrad's paper, my apologies; the material is somewhat beyond me.)

For small values of $n$ and $(a, n) = 1$ it is sometimes possible to give an elementary proof that there are infinitely many primes congruent to $a \bmod n$ along the lines of Euclid's classic proof of the infinitude of the primes. The idea is to find a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $a \bmod n$ or $1 \bmod n$, and such that the first case occurs infinitely many times; then one proves, just as Euclid did, that the integer values of $p$ are divisible by infinitely many primes, and then one contrives to avoid the residue $1 \bmod n$ (if $a \neq 1$; if $a = 1$ then we take $p(t) = \Phi_n(t)$.) Results of Schur and Murty (see this paper of Keith Conrad) then imply that such a polynomial $p$ exists if and only if $a^2 \equiv 1 \bmod n$.

Say that a subset $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ has property E if there exists a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $s \bmod n$ or $1 \bmod n$ for some $s \in S$, and such that the first case occurs infinitely many times. Then we know that any $S$ containing an element squaring to $1$ has property E.

However, there exist subsets $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ not containing such an element with property E. For example, let $G$ be a proper subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$, let $a \not \in G$, and consider

$$p(t) = nt + a.$$

Any prime divisor of $n + a$ is relatively prime to $a$, and at least one of these prime divisors must have residue $\bmod n$ not in $G$. If $p_1, ... p_k$ are finitely many such primes, then $p(p_1 ... p_k) \equiv a \bmod n$ and hence must have a prime factor with the same property which moreover is relatively prime to each $p_i$. It follows that $S = (\mathbb{Z}/n\mathbb{Z})^{\ast} - G$ has property E, and if $n$ does not divide $24$, then taking $G$ to be the subgroup of square roots of $1$ gives the desired example.

Question: What subsets $S$ of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ have property E and are minimal under inclusion? Are they closed under non-empty intersection?

(If this question is somehow answered in Conrad's paper, my apologies; the material is somewhat beyond me.)