Rational Numbers in an Interval

Let the rational number be $\frac{a}{b}$ with $a$ and $b$ are coprime integers. Here, we are just need to find how many positive integers $a$ that less than $b$ , with $\gcd(a,b)=1$ , so, it is just equivalent to compute $\varphi(2)+\varphi(3)+\varphi(4)+\cdots+\varphi(10)$ which is equal to $31$

We are done ;)

If a rational fraction is expressed in lowest terms, then the denominator and the numerator are co-prime to each other.All the numbers in the interval $(0,1)$ are greater than $0$ and less than $1$ .

All the rational numbers in the interval $(0,1)$ can be expressed as $\frac{a}{b}$ where $a,b \epsilon N$ and $1 \leq a<b \leq 10$ .So, $b$ can be any positive integer less than $10$ instead of $1$ and there may be multiple possible numbers of $a$ for each $b$ . So, for every $b$ , there are $\phi(b)$ possible numbers of $a$ . For any number $n$ , $\phi(n)$ refers to the number of co-prime numbers smaller than $n$ . Since, for each $b$ , there are $\phi(b)$ , numbers of $a$ s. So, there are $\phi(b)$ rational fractions for each distinct possible denominator $b$ .

So, the number of possible rational fractions in this case is equal to $\displaystyle \sum_{b=2}^{10}\phi(b)$ .

We can easily proof that, $\phi(n) = n(1 - \frac{1}{p_1})(1-\frac{1}{p_2})......(1-\frac{1}{p_k})$ where $n =(p_1)^{q_1}\times(p_2)^{q_2}\times....\times(p_k)^{q_k}$ where $p_1,p_2,p_3,.....p_k$ are $n$ 's prime factors.

So, $\displaystyle \sum_{b=2}^{10}\phi(b)$ $= \phi(2) + \phi(3) + \phi(4) + \phi(5) +..... + \phi(9) + \phi(10)$ $=1 + 2 + 2 + 4 + 2 +6 + 4 + 6 + 4$ $=31$

So, $31$ rational numbers in the interval $(0,1)$ which agrees with all the given conditions.

Let $\frac {a}{n}$ be the rational in the set. Before finding the answer for the problem, the conditions given must be satisfied.

1. From the given interval $(0,1)$ the values for $a$ should be $1 \leq a < n$

2. The values for $n$ and considering condition 1, should be an integer $2 \leq n \leq 10$

3. The rational must be in lowest term, in other words, $a$ and $n$ must be co-primes or do not have a common factor.

From condition 2, we can say the possible denominators ${2, 3, 4, 5, 6, 7, 8, 9, 10}$ . And from condition 3, $\gcd (a, n) = 1$ we will use Euler's totient function on each of the possible denominators to find the number of its co-primes in the interval $(0, 1)$ which satisfies condition 1. By that, the sum of the number of co-primes from each of the possible denominators should be the number of rationals in the set.

So let $S$ be the number of rationals that satisfies all of the condition. $S = \displaystyle \sum_{i=2}^{10} \varphi (i) = \varphi (2) + \varphi (3) + \varphi (4) + \varphi (5) + \varphi (6) + \varphi (7) + \varphi (8) + \varphi (9) + \varphi (10)$ . Which will lead to, $1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 + 4 = 31$

Lets name A a set that contains only the numbers satisfying our restrictions. x is in A <=> ( there exists a positive non zero integer k) & (there exists a postive integer d) such that GCD(k,d)=1 and x=d/k & k is less than or equal to 10 & 0<x<1 <=> ( there exists a positive non zero integer k) & (there exists a postive integer d) such that GCD(k,d)=1 and x=d/k & k is in the set {2;3;4;5;6;7;8;9;10} ( we excluded 1 because if k=1 then x=d & 0<d<1 hence x is not an integer hence this is a contradiction ) & 0<d<k

+if k=2 then d=1 hence x has 1 possibility here

+if k=3 then d is in the set {1;2} hence x has 2 possibility here

+if k=4 then d is in the set {1;3} hence x has 2 possibility here

+if k=5 then d is in the set {1;2;3;4} hence x has 4 possibility here

+if k=6 then d is in the set {1;5} hence x has 2 possibility here

+if k=7 then d is in the set {1;2;3;4:5;6} hence x has 6 possibility here

+if k=8 then d is in the set {1;3;5;7} hence x has 4 possibility here

+if k=9 then d is in the set {1;2;4;5;7;8} hence x has 6 possibility here

+if k=10 then d is in the set {1;3;7;9} hence x has 4 possibility here

According to the rule of addition the number of possible values x can take is : 4+6+4+6+2+4+2+2+1=31

if a/b is in its lowest form, then a and b are co-prime. So , in this problem all we have to do is to sum up the number of co-prime integers less than the number, for the numbers 2-10. This is due to the constraint a/b < 1. This number is also known as Euler's totient function. So adding up. we get 31.

For a rational number to be expressed in lowest terms, both the numerator and the denominator must be coprime or relatively prime. For a rational number to be valid, the numerator must be coprime with the denominator and the denominator must be equal to or less than 10. Since we are excluding 0 and 1, we start with the numbers that are coprime with 2. (The number must have a smaller value than 2) This gives us 1. Then, we must find the numbers that are coprime with 3 and less than 3. This gives us 1 and 2. We repeat this process until we get to 10. Finally, we add the numbers together. We get 9+4+5+3+4+1+3+1+1 giving us an answer of 31.

First we observe that since the fraction is expressed in lowest terms,

therefore the denominator can only range from 2 to 10 inclusive

2, 3, 5, 7 are prime numbers, they can only be divided by 1 and themselves,

thus there are (2-1)+(3-1)+(5-1)+(7-1) = 13 fractions that satisfy the requirement

for composite numbers 4, 6, 8, 9 and 10

4 = 2^2

6 = 2*3

8 = 2^3

9 = 3^2

10 = 2*5

there are (4-1-1) + (6-1-2-1) + (8-1-3) + (9-1-2) + (10-1-4-1) = 18 fractions

adding them up, 13 + 18 = 31

for denominators for 2 to 10 :

for denominator 10 nominator could be : 1,3,7,9

for denominator 9 nominator could be : 1,2,4,5,7,8

for denominator 8 nominator could be : 1,3,5,7

for denominator 7 nominator could be : 1,2,3,4,5,6

for denominator 6 nominator could be : 1,5

for denominator 5 nominator could be : 1,2,3,4

for denominator 4 nominator could be : 1,3

for denominator 3 nominator could be : 1,2

for denominator 2 nominator could be : 1

so we got 31 rational numbers

For any positive integer $n$ , there are $n-1$ numbers in the interval $(0,1)$ that can be expressed with denominator $n$ , namely the numbers $\frac{1}{n}, \frac{2}{n}, \ldots, \frac{n-1}{n}$ . However, when we have different values of $n$ , these numbers are not necessarily distinct. If, for each value of $n$ , we only count the number of such fractions which are in lowest terms, we will get the desired answer. For any $n$ , the number of such fractions will be $\phi(n)$ . Thus, our total number of fractions will be $\phi(2) + \phi(3) + \cdots + \phi(10) = 1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 + 4 = 31$ .