Skip to main content
Back to Sets, Relations & Functions
JEE Main 2020
Sets, Relations & Functions
Sets and Relations
Medium

Question

Let A={1,2,3,,10}A=\{1,2,3, \ldots, 10\} and B={mn:m,nA,m<nB=\left\{\frac{m}{n}: m, n \in A, m< n\right. and gcd(m,n)=1}\left.\operatorname{gcd}(m, n)=1\right\}. Then n(B)n(B) is equal to :

Options

Solution

1. Key Concepts and Formulas

  • Set Theory: Understanding set notation and how to define elements within a set.
  • Number Theory: The concept of the Greatest Common Divisor (GCD) and its property that gcd(a,b)=1\operatorname{gcd}(a, b) = 1 means aa and bb are relatively prime (coprime).
  • Systematic Enumeration: A method of listing all possible elements that satisfy given conditions to count them accurately.

2. Step-by-Step Solution

Step 1: Understand the Set Definitions and Conditions We are given set A={1,2,3,,10}A = \{1, 2, 3, \ldots, 10\} and set B={mn:m,nA,m<n and gcd(m,n)=1}B = \left\{\frac{m}{n}: m, n \in A, m<n \text{ and } \operatorname{gcd}(m, n)=1\right\}. We need to find the number of elements in set BB, denoted as n(B)n(B). The conditions for an element mn\frac{m}{n} to be in BB are:

  1. mAm \in A and nAn \in A: Both mm and nn must be integers from 1 to 10, inclusive.
  2. m<nm < n: The numerator must be strictly less than the denominator. This implies that mm can range from 1 to 9, and for each mm, nn must be greater than mm and at most 10.
  3. gcd(m,n)=1\operatorname{gcd}(m, n) = 1: The numerator and denominator must be relatively prime, meaning the fraction is irreducible.

Step 2: Systematically List Valid Pairs (m,n)(m, n) We will iterate through all possible values of mm from 1 to 9 (since m<nm<n and n10n \le 10, mm cannot be 10) and for each mm, find the possible values of nn from the set {m+1,m+2,,10}\{m+1, m+2, \ldots, 10\} such that gcd(m,n)=1\operatorname{gcd}(m, n) = 1.

  • For m=1m=1:

    • Possible nn values are {2,3,4,5,6,7,8,9,10}\{2, 3, 4, 5, 6, 7, 8, 9, 10\}.
    • gcd(1,n)=1\operatorname{gcd}(1, n) = 1 for all nn.
    • Valid pairs: (1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10)(1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10).
    • Count: 9.
  • For m=2m=2:

    • Possible nn values are {3,4,5,6,7,8,9,10}\{3, 4, 5, 6, 7, 8, 9, 10\}.
    • We need gcd(2,n)=1\operatorname{gcd}(2, n) = 1, so nn must be odd.
    • Valid nn: {3,5,7,9}\{3, 5, 7, 9\}.
    • Valid pairs: (2,3),(2,5),(2,7),(2,9)(2,3), (2,5), (2,7), (2,9).
    • Count: 4.
  • For m=3m=3:

    • Possible nn values are {4,5,6,7,8,9,10}\{4, 5, 6, 7, 8, 9, 10\}.
    • We need gcd(3,n)=1\operatorname{gcd}(3, n) = 1, so nn must not be a multiple of 3.
    • Valid nn: {4,5,7,8,10}\{4, 5, 7, 8, 10\}. (Exclude 6, 9).
    • Valid pairs: (3,4),(3,5),(3,7),(3,8),(3,10)(3,4), (3,5), (3,7), (3,8), (3,10).
    • Count: 5.
  • For m=4m=4:

    • Possible nn values are {5,6,7,8,9,10}\{5, 6, 7, 8, 9, 10\}.
    • We need gcd(4,n)=1\operatorname{gcd}(4, n) = 1. Since 4=224=2^2, nn must be odd.
    • Valid nn: {5,7,9}\{5, 7, 9\}. (Exclude 6, 8, 10).
    • Valid pairs: (4,5),(4,7),(4,9)(4,5), (4,7), (4,9).
    • Count: 3.
  • For m=5m=5:

    • Possible nn values are {6,7,8,9,10}\{6, 7, 8, 9, 10\}.
    • We need gcd(5,n)=1\operatorname{gcd}(5, n) = 1, so nn must not be a multiple of 5.
    • Valid nn: {6,7,8,9}\{6, 7, 8, 9\}. (Exclude 10).
    • Valid pairs: (5,6),(5,7),(5,8),(5,9)(5,6), (5,7), (5,8), (5,9).
    • Count: 4.
  • For m=6m=6:

    • Possible nn values are {7,8,9,10}\{7, 8, 9, 10\}.
    • We need gcd(6,n)=1\operatorname{gcd}(6, n) = 1. This means nn must not be divisible by 2 or 3.
    • Valid nn: {7}\{7\}. (Exclude 8 (divisible by 2), 9 (divisible by 3), 10 (divisible by 2)).
    • Valid pair: (6,7)(6,7).
    • Count: 1.
  • For m=7m=7:

    • Possible nn values are {8,9,10}\{8, 9, 10\}.
    • We need gcd(7,n)=1\operatorname{gcd}(7, n) = 1. Since 7 is prime, nn must not be a multiple of 7.
    • Valid nn: {8,9,10}\{8, 9, 10\}. (None are multiples of 7).
    • Valid pairs: (7,8),(7,9),(7,10)(7,8), (7,9), (7,10).
    • Count: 3.
  • For m=8m=8:

    • Possible nn values are {9,10}\{9, 10\}.
    • We need gcd(8,n)=1\operatorname{gcd}(8, n) = 1. Since 8=238=2^3, nn must be odd.
    • Valid nn: {9}\{9\}. (Exclude 10 (even)).
    • Valid pair: (8,9)(8,9).
    • Count: 1.
  • For m=9m=9:

    • Possible nn value is {10}\{10\}.
    • We need gcd(9,n)=1\operatorname{gcd}(9, n) = 1. Since 9=329=3^2, nn must not be a multiple of 3.
    • Valid nn: {10}\{10\}. (10 is not a multiple of 3).
    • Valid pair: (9,10)(9,10).
    • Count: 1.

Step 3: Sum the Counts to Find n(B)n(B) The total number of elements in set BB is the sum of the counts from each case of mm: n(B)=9+4+5+3+4+1+3+1+1=31n(B) = 9 + 4 + 5 + 3 + 4 + 1 + 3 + 1 + 1 = 31

3. Common Mistakes & Tips

  • Forgetting GCD Condition: Failing to check gcd(m,n)=1\operatorname{gcd}(m, n)=1 will lead to including reducible fractions like 24\frac{2}{4} or 36\frac{3}{6}, overcounting the elements.
  • Incorrect Range for nn: Ensure nn is always strictly greater than mm and not exceeding 10. For example, when m=9m=9, nn can only be 10.
  • Systematic Checking: For composite mm, remember that gcd(m,n)=1\operatorname{gcd}(m, n)=1 implies nn is coprime to all prime factors of mm. For instance, gcd(6,n)=1\operatorname{gcd}(6, n)=1 means nn is not divisible by 2 and not divisible by 3.

4. Summary We identified the conditions for elements in set BB: m,nm, n are from {1,,10}\{1, \ldots, 10\}, m<nm < n, and gcd(m,n)=1\operatorname{gcd}(m, n) = 1. By systematically iterating through all possible values of mm from 1 to 9 and finding the corresponding valid values of nn that satisfy m<n10m < n \le 10 and gcd(m,n)=1\operatorname{gcd}(m, n) = 1, we counted the total number of such pairs. Summing the counts for each mm gives the total number of elements in set BB.

5. Final Answer The total number of elements in set BB is 3131. This corresponds to option (A). The final answer is 31\boxed{\text{31}}.

Practice More Sets, Relations & Functions Questions

View All Questions