0
$\begingroup$

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<n\}$$ 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

$\endgroup$
0
$\begingroup$

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\}$.

$\endgroup$
-2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.