I am trying to solve $x^2-1=0\mod 24$. First I use a theorem which states that $\mathbb{Z}/n \simeq \mathbb{Z}/p_1^{r_1} \times \cdots \times \mathbb{Z}/p_k^{r_k}$, where $p_1^{r_1}\cdots p_k^{r_k}$ is the prime factorization of $n$. Then since $24 = 2^3\cdot 3$, we can solve two congruence equations:
$$
x_1 := \{x \in \mathbb{Z}/8 : x^2-1 = 0 \mod 2^3 \} \qquad x_2:=\{x\in\mathbb{Z}/3 : x^2-1 = 0 \mod 3\}
$$
Its easy enough to show that $x_1 = \{1,3,5,7\}$, and $x_2 =\{1,2\}$. But then the next step is to combine them together to get all of the solutions modulo $24$. This is where I am getting confused because the notes say that the solution is: $x = \{1,5,7,11,13,17,19,23\}$, but I don't see where all of these extra numbers are coming from, or how the above theorem is being applied to get these extra solutions. I know that the theorem implies that the number of solutions in $\mathbb{Z}/24$ will be equal to $\lvert x_1\rvert\lvert x_2\rvert=8$, but where the specific numbers come from I have no idea. Any advice or suggested readings would be appreciated!
Solving a Congruence Relation with a function
elementary-number-theorymodular arithmetic
Best Answer
There are no extra numbers there. The numbers that you mentioned are the numbers from the set $\{0,1,2,\ldots,23\}$ wich are simultaneously congruent with $1$, $3$, $5$, or $7$ modulo $8(=2^3)$ and congruent with $1$ or $2$ modulo $3$. Take $19$, for instance, and note that $19\equiv3\pmod8$ and that $19\equiv1\pmod3$.