1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ $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. $\endgroup$ – lulu May 20 '20 at 13:43
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

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