A fraction $p/q<1$ such that $p+q=333$.

Question

Let $p/q<1$ and $p+q=333$. Show that the number of fractions where $p$ and $q$ has no common factor is $108$.

This is what I’ve worked out: $333/2 = 166.5$, and since $p<q$,

$p\leq 166, $ $q \geq 167$

So the total number of fractions is $166$.

But I don’t know how to find the number of fractions where $p$ and $q$ has no common factor without listing them all out.

Answer 1

$$333=3^2\cdot37.$$ Thus, by your work it's $$166-\left[\frac{166}{3}\right]-\left[\frac{166}{37}\right]+1=108.$$

Answer 2

Note that any common factor of $p$ and $q$ must divide their sum, i.e., $333 = 3 \times 3 \times 37$. So among the $166$ possible sets of values, the only ones to exclude are those where $p$ and $q$ have prime factors of $3$ and/or $37$. You can use the Inclusion–exclusion principle to determine the number of values with one or both of these factors is

$$\left\lfloor \frac{166}{3} \right\rfloor + \left\lfloor \frac{166}{37} \right\rfloor - \left\lfloor \frac{166}{3 \times 37} \right\rfloor = 55 + 4 - 1 = 58 \tag{1}\label{eq1}$$

Thus, the # of values which pass, i.e., have no common factor, is

$$166 - 58 = 108 \tag{2}\label{eq2}$$

Answer 3

The fractions are $\frac n{333-n}$ where $n \le 166$

We have $\gcd(333-n, n) =1$.

If $p|n$ and $p|333 -n$ then it follows that $p|333$.

But $333 = 3^2*37$. So $n$ can not have $3$ or $37$ as a divisor.

(Think about it. If $n = 3k$ then $\frac {3k}{333 - 3k} = \frac {3k}{3(111-k)}$ and that is not in lowest terms. Likewise if $n = 37j$ then $\frac {37j}{333-37j} = \frac {37j}{37(9-j)}$ is not in lowest times.)

(But if $3\not \mid n$ and $37\not \mid n$ so if $a|n$, then $a \not\mid n$ and we can't factor an $a$ out of both $n$ and out of $333-n$. So $\frac n{333-n}$ is in lowest terms.)

So we need to count all the $n: n \le 166$ and $37\not \mid n$ and $3\not \mid n$.

Can you think about how you might solve this?

$n=3,6,9,12,......,165$ are divisble by $3$ so those are all out. And there are $\frac {165}{3} = 55$ multiples of $3$. So none of those are good.

And if $n = 37, 74, 111, 148$ are divisible by $37$ and those are all out.

There are $166$ possible $n$. If we remove the $55$ multiples of $3$ we have $111$ left. If we remove the four multiples of $4$ we have $107$ left.

But do you see the mistake we made?

We dismissed $111$ as a multiple of $3$. And then we dismissed it again as a multiple of $37$. We dismissed it twice. We should have only dismissed it once.

So if we start with $166$. Dismiss the $55$ multiples of $3$, then dismiss the $4$ multiples of $37$, but add the one back that we dismissed twice. $166-55-4+1 = 108$.

You need to count all the $n$ so that $1\le n\le 166$ and $\gcd(n, 366-n) = 1$.