AIME I problem #3

assume that the number takes the form $\frac{a}{b}$ .

Where a and b are coprime and a+b=1000

$\therefore, a=1000-b$

Rewriting our fraction yields

$\dfrac{1000-b}{b}$

$\dfrac{1000}{b}-\dfrac{b}{b}$

Note that this means that b must be coprime with 1000, aka, not divisible by 2 or 5 since is must be unsimplifyable.)

The largest value of a is 499 and the min for b is 501, since a<b for $\frac{a}{b}<1$

Now, here's the main reason I posted this. I wanted to show a small short cut to the continuation of the problem. The first 3/4ths of my solution is the same, but the last quarter (this half) is different.

We need to find all numbers co-prime to 1000, but less than 500, using Euler's totient function ( $\phi$ ) on 1000 would give us numbers greater than 500, thus, to find out the answer, we will compute $\phi (500)$ . In the short: The totient function is simply then number times 1-1/each prime factor multiplied out and it finds the number of numbers less then n coprime to n.

$\boxed{\phi{500}=500(1-\frac{1}{2})(1-\frac{1}{5})=200}$

We have that the set of these rational numbers is from $\frac{1}{999}$ to $\frac{499}{501}$ where each each element $\frac{n}{m}$ has $n+m =1000$ and $\frac{n}{m}$ is irreducible.

We note that $\frac{n}{m} =\frac{1000-m}{m}=\frac{1000}{m}-1$ . Hence, $\frac{n}{m}$ is irreducible if $\frac{1000}{m}$ is irreducible, and $\frac{1000}{m}$ is irreducible if $m$ is not divisible by $2$ or $5$ . Thus, the answer to the question is the number of integers between $999$ and $501$ inclusive that are not divisible by $2$ or $5$ .

We note there are $499$ numbers between $501$ and $999$ , and

• $249$ of them are divisible by $2$
• $99$ of them are divisible by $5$
• $49$ of them are divisible by $10$

Using the Principle of Inclusion and Exclusion, we get that there are $499-249-99+49=200$ numbers between $501$ and $999$ are not divisible by either $2$ or $5$ , so our answer is $\boxed{200}$ .

If $o< \frac {a}{b} <1$ is in reduced form, then $gcd(a,b)=1$ and $1 \leq a < b$ . If $a+b=1000$ , then the total number should be half of Euler's Totient function at $1000$ , which gives $\boxed{200}$ .

Let's say that the number r takes the form p/q where p and q are coprime integers and p=1000-q (as required).So p/q takes the form (1000/q - 1).We also have Phi(1000)=400.The other requirement is that 0<r<1 => 0< (1000/q - 1)<1 => 1<1000/q<2 => 500<q<1000.Thus we have that q must fall in the range of (500,1000).We have one more requirement that r is written as a fraction in lowest terms which means q must be coprime to 1000.Therefore we need to find all such integers q which are coprime to 1000 and falls in the range (500,1000).

We know that gcd(a,b) =gcd(a-b,a) which means gcd(1000,499)=gcd(501,1000); gcd(1000,498)=gcd(502,1000);. .........gcd(1000,1)=gcd(499,1000). So we have that every coprime to 1000 in the interval [1,500] has sort of its image in [500,1000] and there are equal number of coprimes to 1000 in the intervals [1,500] and [500,1000] and because 500 is not coprime to 1000, the number of coprimes to 1000 in the interval (500,1000)=1/2(Phi 1000)= 400/2=200.Hence there are * 200* such rational numbers.

We are looking for the fractions $0<\frac{a}{1000-a}< 1$ such that $\gcd(a,1000-a)=\gcd(a,1000) = 1$

Thus we are looking for all $1\leq a \leq 500$ such that $\gcd(a,1000)=1$ .

The desired number is $\phi(500) = 200$