Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- User:
- Given a rational number, write it as a fraction in lowest terms and calculate the product of the resulting numerator and denominator. For how many rational numbers between 0 and 1 will $20_{}^{}!$ be the resulting product?
- Assistant:
- We are given a rational number between 0 and 1, written in lowest terms as $\frac{a}{b}$, where $0 < a < b$, $\gcd(a,b) = 1$, and the **product** $a \cdot b = 20!$.
- We are to find **how many** such rational numbers exist.
- ---
- ### Step 1: Understanding the Problem
- We want fractions $\frac{a}{b}$ in lowest terms, $0 < a < b$, such that $a \cdot b = 20!$.
- Since $\gcd(a,b)=1$, and $a \cdot b = 20!$, this means that $a$ and $b$ are **coprime** positive integers whose product is $20!$, and $a < b$.
- So, essentially, we need to find the number of **ways to split the prime factors of $20!$ into two coprime parts $a$ and $b$**, such that $a < b$ and $a \cdot b = 20!$.
- Because $a$ and $b$ are coprime and their product is $20!$, each prime factor of $20!$ must go entirely to $a$ or entirely to $b$. So this is equivalent to **partitioning the set of prime factors of $20!$** into two disjoint subsets: one for $a$, one for $b$.
- But note: $20!$ has prime factors all primes ≤ 20.
- Let’s list the primes ≤ 20:
- $$
- 2, 3, 5, 7, 11, 13, 17, 19
- $$
- So there are **8 distinct prime factors**.
- Now, for each prime $p$, all copies of $p$ in $20!$ must go entirely to $a$ or entirely to $b$, because if $a$ and $b$ are coprime, they share no prime.
- So, for each prime, assign it to $a$ or to $b$: $2^8 = 256$ ways.
- Each such assignment defines a unique pair $(a,b)$ with $a \cdot b = 20!$ and $\gcd(a,b)=1$.
- But note: $a$ and $b$ must be **positive integers**, and since the fraction is between 0 and 1, $a < b$.
- Also, since $a \cdot b = 20!$, and $a \ne b$ (unless $20!$ is a square, which it’s not, because exponents of primes like 19 are 1), so $a \ne b$ always.
- So the 256 assignments give 256 **ordered** pairs $(a,b)$ with $a \cdot b = 20!$, $\gcd(a,b)=1$. But since $a$ and $b$ are determined by which primes go to $a$, and the rest to $b$, each subset $S$ of the 8 primes defines $a = \prod_{p \in S} p^{v_p(20!)}$, $b = 20!/a$.
- Now, among these 256 pairs, exactly half will have $a < b$, half $a > b$, because $a \leftrightarrow b$ is a bijection and $a \ne b$.
- So total number of unordered coprime pairs $\{a,b\}$ with $a \cdot b = 20!$ is $2^{7} = 128$, since each pair is counted twice.
- But we want **fractions between 0 and 1**, so $a < b$, hence exactly **128** such fractions.
- Wait — is that correct?
- Let’s verify.
- Total number of ways to assign each prime to $a$ or $b$: $2^8 = 256$.
- Each assignment gives a unique $(a,b)$ with $a \cdot b = 20!$, $\gcd(a,b)=1$.
- Now, since $a \ne b$ (as $20!$ is not a square — because prime 19 appears only once, so in any factorization $a \cdot b$, one of $a$ or $b$ has 19, the other doesn’t, so they can’t be equal), then exactly half of these 256 assignments have $a < b$, half $a > b$.
- So number of fractions $\frac{a}{b} \in (0,1)$ in lowest terms with $a \cdot b = 20!$ is $256 / 2 = 128$.
- But wait — is every such assignment valid? Yes, because once you assign all copies of a prime to $a$ or $b$, $a$ and $b$ are determined and coprime.
- So the answer should be $2^{7} = 128$.
- But let’s double-check with a small example.
- Suppose instead of $20!$, take $6! = 720$.
- Primes ≤6: 2,3,5 → 3 primes.
- Number of coprime pairs $(a,b)$ with $a \cdot b = 720$, $a < b$: $2^{2} = 4$?
- Let’s list them.
- We must assign each prime power fully to $a$ or $b$.
- $720 = 2^4 \cdot 3^2 \cdot 5^1$
- So possible $a$ (coprime to $b=720/a$):
- - $a=1$, $b=720$ → product 720, $a < b$
- - $a=2^4=16$, $b=45$ → $\gcd(16,45)=1$, 16<45
- - $a=3^2=9$, $b=80$ → gcd(9,80)=1, 9<80
- - $a=5$, $b=144$ → gcd=1, 5<144
- - $a=16*9=144$, $b=5$ → but then $a > b$
- - $a=16*5=80$, $b=9$ → $a > b$
- - $a=9*5=45$, $b=16$ → $a > b$
- - $a=16*9*5=720$, $b=1$ → $a > b$
- So the 4 with $a < b$: $a=1,5,9,16$
- Yes, $2^{3-1} = 4$. So pattern holds.
- Thus for 8 primes, answer is $2^{7} = 128$.
- ---
- ### Final Answer:
- $$
- \boxed{128}
- $$
Advertisement
Add Comment
Please, Sign In to add comment