A question about counting multiples of factors

Question

My question is best explained by an example:

Say I have the number 12. By the fundamental theorem of arithmetic I know that I have some unique prime factorization of it. It's $2 \cdot 2 \cdot 3$ and so I know that if can divide it by 2 and 3.

Now, if I divide by 2, I get 6. That tells me there are 6 different numbers with two as a factor between 12 and 2: 2, 4, 6, 8, 10, 12. If I divide by 3, I get 4. That means I have 4 different numbers with three as a factor between 12 and 3: 3, 6, 9, 12. If I add all those up, I have a total of 10 factor, but there are some doubles. 6 and 12.

So, technically I only have 8 unique numbers which have 2 or 3 as factors between 2 and 12: 2, 3, 4, 6, 8, 9, 10, 12

Is there a quick way to discern how many numbers might exist? Right now I'm just doing 12/2 = 6, 6/3 = 2 $\Rightarrow $ 6 + 2 = 8 and it seems to work sometimes but not all the time so I know it's not efficient and I'm just getting lucky.

Answer 1

So? You are asking how many numbers are not relatively prime to $M$. Google Euler's totient function. THat tells you how many are relatively prime. Just subtract. $\phi(M) = $ number of integers relatively prime to $M$ then $M - \phi(M)$ are the number of integers that are not.

Goggle it but the upshot is $\phi(\prod p_i^{\alpha_i}) = \prod (p_i - 1)\prod p_i^{\alpha_i - i}$.

So For $12 = 2^2 *3 $, $\phi(12) = (2-1)*2^1 *(3-1)*3^0 = 4$. The numbers that are relatively prime are $1,5,7,11$ and so the $8$ that are not are $2,3,4,6,8,9,10,12$.

Another way to view it is $\phi (n) = n*\prod_{p|n; p\text{prime}}(1- \frac 1k)$ so $\phi (12) = 12\prod_{2,3} (1 - \frac 1p) = 12(\frac 12)(\frac 23)= 4$.

Read up on it. You have the right idea.

https://en.wikipedia.org/wiki/Euler%27s_totient_function

The main things are $\phi(nm) = \phi(n)\phi(m)$ if $\gcd(n,m) = 1$ (read up on the chinese remainder theorem. And $\phi(p^k)$ for prime $p$ is $n-\frac n/p$ (as $p, 2p, 3p.....\frac np*p$ are not).

I

Answer 2

For any finite set $A$ let #$(A)$ be the number of members of $A.$ Then for finite sets $A,B$ it follows that #($A\cup B)=$#$(A)\;+\;$#$(B)-\;$#$(A\cap B)$ because if we count $A$ and count $B$ and add, we have counted each member of $A\cap B$ twice, so we must subtract #$(A\cap B)$ from #$(A)+$#($B)$ in order to get #$(A+B)$. So you weren't lucky. You were right.

Similarly #$(A\cup B\cup C)=$#$(A)+$#$(B)+$#$(C)-$#($A\cap B)-$#($B\cap C)-$#$(C\cap A)+ $ #$(A\cap B \cap C).$ (And so on for $A,B,C,D$,etc.)

Applying this to the Q involving factors, this would be a very inefficient method when, instead of $12$ or $15,$ you began with a number with many prime factors. Instead ,use the method in the A from Fleablood.