# How to count the number of elements in the given set

I am stuck at this counting. I am explaining my question with an example.

Suppose we take $$n=2\times 3\times 5\times 7$$. I want to find those elements in the set $$X=\{7,14,21,28,35,42,49,56,\ldots ,203\}=\{7k\,|\, 1\leqslant 7k which have $$2,3,5$$ as one of their prime factors and count their number. I call this number $$x$$.

The numbers in the set $$X$$ which have $$2,3,5$$ as one of their prime factors are $$\{14,21,28,35,42,56,63,70,84,98,105,112,126,140,147,154,175,182,189,196\}.$$

I took the subgroup generated by $$2\times 7=14$$ which is $$\{0,14,28,42,\ldots,196\}$$. I took the subgroup generated by $$3 \times 7=21$$ which is $$\{0,21,42,63,\dots,189\}$$. I took the subgroup generated by $$5\times 7=35$$ which is $$\{0,35,70,105,\dots,175\}$$.

I found $$x=$$ number of elements in subgroup generated by $$14$$ + number of elements in subgroup generated by $$21$$+number of elements in subgroup generated by $$35$$ -number of elements in subgroup generated by $$42$$-number of elements in subgroup generated by $$70$$-number of elements in subgroup generated by $$105=15+10+6-6-3-2=20$$.

My question is:

If $$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$$ and if we consider the cyclic subgroup generated by $$p_k$$ denoted by $$\langle p_k\rangle$$, what will be the number of those elements in $$\langle p_k\rangle$$ which have $$p_i$$ where $$1\le i\le k-1$$ as one of their prime factors?

I have provided as much detail as I could. If I need to provide any other details please ask in the comment box

Regarding the example: Let's allow $$0$$ in $$X$$, then $$X = 7\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} =: R$$, where $$m = 2\cdot 3\cdot 5$$. You are searching for the number $$x$$ of Elements in $$X$$ which share a factor with $$|R| = m$$. Below I show that the number of $$k\in\mathbb{N}, k\leq m$$ which are coprime to $$m$$ is equal to the number of units (invertible elements) in $$R$$, which is given by $$\varphi(m)$$, where $$\varphi$$ is Euler's totient function. Finally you get $$x = m - \varphi(m) - 1 = 30 - 8 - 1 = 21$$ (I'm subtracting $$1$$, because $$X$$ contains $$0$$ now. I don't know why our counts are off by one, though)

Edit: I just noticed I haven't really answered your generalized question, but I'd say it works just like in the special case from above.

Proof of the claim from above.

Let $$\varphi : \mathbb{N} \longrightarrow \mathbb{N}, n \longmapsto |E(\mathbb{Z}_n)|$$ and $$M_n := \{k\in\mathbb{N} \mid k \leq n,\; \gcd(k,n) = 1 \}$$. We show $$|M_n| = \varphi(n)$$. Choose an arbitrary $$n\in\mathbb{N}$$.

''$$\leq$$'': Let $$m \in M_n$$. Then the Euclidian algorithm gives $$k,\ell \in \mathbb{Z}$$ such that $$1 = km + \ell n$$. I.e., $$\bar 1 = \overline{km} + \overline{\ell n} = \overline{km}$$ in $$\mathbb{Z}_n$$, thus $$(\bar m)^{-1} = \bar k$$ and thus $$\bar m \in E(Z_n)$$. Because $$m \leq n$$ for all $$m \in M_n$$, we get $$\bar m' \neq \bar m$$ for $$m'\neq m \in M_n$$.

''$$\geq$$'': Let $$\bar m \in E(\mathbb{Z}_n)$$. Then there is $$k \in \mathbb{Z}$$ such that $$1 = \overline{mk}$$, hence there is $$\ell \in \mathbb{Z}$$ such that $$1 = km + \ell n$$. Thus $$1 \in m\mathbb{Z} + n\mathbb{Z} = d\mathbb{Z}$$. Such a $$d\in\mathbb{Z}$$ exists, because $$\mathbb{Z}$$ is a principle ideal domain. Then $$d$$ is a gcd of $$n$$ and $$m$$. From $$1 \in d\mathbb{Z}$$ follows $$d\mathbb{Z} = \mathbb{Z}$$ and therefore $$d\in \{1,-1\}$$.

If you are talking about arithmetic sequence , you can easily count the number of its elements using this formula :
$$a_{n} = a_{1} + (n-1)d$$
where, $$a_{n}$$ is the last number in the arithmetic sequence, $$a_{1}$$ is the first number, $$n$$ is number of elements ,and $$d$$ is the difference between any two successive elemets

So in your question the number of elements in the set is : $$n=29$$ using the above formula