# Finding two common divisors of $n$ and $80$

The positive integers $$34$$ and $$80$$ have exactly two positive common divisors, namely $$1$$ and $$2$$. How many positive integers $$n$$ with $$1 ≤ n ≤ 30$$ have the property that $$n$$ and $$80$$ have exactly two positive common divisors?

I don't think the question was very clear here, are we essentially looking for pairs of divisors of $$30$$ and $$80$$ or $$34$$ and $$80$$?

Prime factoring each one of these results in $$34 = 2 \cdot 17$$, $$80 = 2^4 \cdot 5$$ and $$30 = 2\cdot 5\cdot3$$. Is this of any help in order to find the answer?

• $34$ has nothing to do with the question, they just included that to illustrate what they are asking. You are asked to count the number of $n\in \{1, \cdots, 30\}$ such that $n$ and $80$ have exactly two common divisors. For example, $n=1$ does not work but $n=2$ does. – lulu May 20 '20 at 13:43

$$n$$ and $$m$$ have exactly two positive common divisors if and only if $$\gcd(n,m)$$ is a prime $$p$$. Then the two common divisors are $$1$$ and $$p$$. Since $$80 = 2^4 \cdot 5$$ we have two cases:

1) $$\gcd(n,80)=2$$, i.e. $$n$$ is divisible by $$2$$, but not by $$5$$ and $$4$$.

2) $$\gcd(n,80)=5$$, i.e. $$n$$ is divisible by $$5$$, but not by $$2$$.

How many positive integers $$n$$ with $$1\leq n\leq N$$ have this property?

The answer is $$N_1+N_2$$ where, by the inclusion–exclusion principle, $$N_1=\lfloor N/2\rfloor- \lfloor N/10\rfloor- \lfloor N/4\rfloor+ \lfloor N/20\rfloor$$ and $$N_2=\lfloor N/5\rfloor- \lfloor N/10\rfloor.$$

Yes, the prime factorization is your best friend here! Notice that $$80$$ and $$34$$ have only one nontrivial factor in common, because there exists exactly one prime $$p$$ dividing $$80$$ and $$34$$ simultaneously.

To answer a question, here is a reasonable method, given we are dealing with small numbers:

1. Pick a prime factor $$p$$ of $$80$$.

2. Then you can pick any prime numbers $$q_1, \cdots, q_n$$ (as many as you like, and repeats are allowed) that all do not divide $$80$$, and multiply all of them together, along with $$p$$.

You just need to ensure at the end that the product $$p q_1 q_2 \cdots q_n$$ is at most $$30$$.

Slicker Solution: We can observe from the previous solution that $$x$$ and $$y$$ share exactly one nontrivial divisor if and only if $$x = ap$$ and $$y = bp$$ for some prime $$p$$ where $$\gcd(a, b) = 1$$. Since $$x = 80 = 2^4 \cdot 5$$, there are two candidates for $$p$$ here: $$2$$ and $$5$$. If $$p = 2$$, then $$a = 40$$, and hence the candidates for $$b$$ in this case are the numbers that are relatively prime to $$40$$. Imposing the condition that $$y \leq 30$$, we only need to count the numbers that are relatively prime to $$40$$ less than or equal to $$y / p = 15$$. If $$p = 5$$, then the candidates for $$b$$ in this case are those relatively prime to $$16$$, and we need to check only those up to $$y / p = 6$$.

In fact, it gets better: we have not overcounted a number in these two cases! To see why this is, note that we isolated $$2$$ cases: one was when $$y = 2b$$, and the other was when $$y = 5b'$$, where $$\gcd(b, 40) = 1$$ and $$gcd(b', 16) = 1$$. We would have overcounted if $$2b = 5b'$$ for some values of $$b$$ and $$b'$$. However, $$2b$$ cannot equal $$5b'$$, because $$5$$ cannot divide $$b$$ (otherwise, $$\gcd(b, 40) \geq 5$$). This result makes for a nice general algorithm. To count how many numbers $$1 \leq y \leq m$$ share exactly one nontrivial divisor with a number $$x$$ with prime factorization $$p_1^{k_1} p_2^{k_2} \cdots p_m^{k_n}$$, where $$y \leq x$$, we just need to sum $$\phi(x / p_1, \lfloor y / p_1 \rfloor) + \phi(x / p_2, \lfloor y / p_2 \rfloor) + \cdots + \phi(x / p_n, \lfloor y / p_n \rfloor)$$ where $$\phi(\alpha, \beta)$$ is a modified version of the Euler Totient Function counting how many numbers less than $$\beta$$ that $$\alpha$$ is coprime with.