See for the problem here: Click here
Correct Answer:
Correct answer was given by Manjunath M R (Infosys), Harshitha K N (Research Scholar, UOM) and Nagendra P (Research Scholar, UOM). However, correct justifications were given by Manjunath M R. and Nagendra. We shall present below the solution by Manjunath M. R. and the original solution (by Dept. Of Mathematics, SVC) along with solution of Nagendra as both are on similar lines.
Note. If you find any mistake, please write us at dep.math.svc@gmail.com
Solutions.
Solution by Manjunath This ingenious solution is comparitively shorter but requires verification of the solution for certain numbers. Verification can be done easily with a computer program as given below. We first prove a lemma which we require.
Lemma: If \(n\) is composite, then \(φ(n) ≤ n - \sqrt{n}\).
Proof. Let \(n = p_1^{r_1}p_2^{r_2}...p_k^{r_k}\). Without loss of generaility, let us suppose that \(p_1\) itself is the smallest prime divisor of \(n\). Then \(p_1 ≤ \sqrt{n}\). We have
(We leave it to readers to think where the fact that \(n\) composite has been used here)
It is easy to see that no prime number \(n\) satisfies the given equation \(n=φ(n)+10\). Assuming \(n\) to be composite, if \(φ(n) = n-10\), then we must have from above lemma that
Thus, if at all such an \(n\) exists satisfying \(n = φ(n)+10\), then \(n ≤ 100\). We used maxima as shown below to see that no \(n ≤ 100\) satisfies the given equation.
Note. The lemma presented above already exists in thr literature. In order to see that it is quite easy to prove, the proof to it has been included above
Original Solution. This is bit lengthier, but constructive one requiring not much computional verification. Here we give proof case by case. We consider four cases: (i) \(n\) divisible by more than three prime distinct prime numbers. (ii) \(n\) divisible by three distinct prime numbers. (iii) \(n\) divisible by two distinct prime numbers (iv) \(n\) divisble by exactly one prime number.
We first prove the following lemma which we require.
Lemma If \(k ≥ 2\) and if \(p_1, p_2, ..., p_k\) are distinct natural numbers each of which is gretaer than 1, then
Proof. We shall prove this by induction on \(k\). This is true for the case of \(k=2\). Suppose the statement is true for some \(k\). We shall show that it must be true for \(k+1\) also. Suppose it is true that
Now, observe
\(p_1p_2...p_k p_{k+1}- (p_1-1)(p_2-1)...(p_k-1)(p_{k+1}-1) \)
\( ≥ p_{k+1}(p_1p_2...p_k - (p_1-1)(p_2-1)...(p_k-1))\)
\(≥ p_{k+1}(p_1+p_2+...+p_k-1)\)
\(≥ p_1+p_2+...+p_k+p_{k+1}-1\).
We leave the justification of the last step to the readers with the hint that if the natural number \(n\) is greater than 1 and if \(m\) is a positive integer, then
Hence by induction, the Lemma is true for all natural numbers \(k≥ 2\).
Now, returning to problem, suppose \(n\) has got the prime factorization,
Then
Hence
Now the second term of the product on the right hand side of the above, that is, \(p_1p_2...p_k - (p_1-1)(p_2-1)...(p_k-1)\) is greater than or equal to \(p_1+p_2+...+p_k-1\) as per the lemma. We now consider four different cases
Case 1 (k ≥ 4): If \(k ≥ 4\), that is if \(n\) is divisible by more than three distinct prime numbers, then we must have
implying that \(n-φ(n) > 10\). We got 16 in the above inequality, because, if \(p_1, p_2, p_3\) and \(p_4\) are any four distinct primes then necessarily
Hence \(n\) cannot have more than 3 prime factors.
Case 2 (k=3): Now, suppose \(k=3\), that is \(n\) has got three distinct prime factors. If at all
then
But \(p_1(p_2-1)+p_2(p_3-1)+p_3(p_1-1) + 1 ≥ 2+3+5+1 = 11 >10 \). Hence it cannot divide 10. Thus \(n\) has got not more than two distinct prime factors.
Case 3 (k=2) Now suppose \(k=2\), that is \(n\) has got two distinct prime factors. If at all
then
But for no two distrinct primes \(p_1\) and \(p_2\), it can happen that \(p_1+p_2-1\) is a factor of 10. Thus \(k\) cannot be 2. Only option left out is, \(k=1\).
Case 4 (k=1): Suppose \(k=1\). Then \(n= p_1^{k_1}\). But then
If \(n-φ(n) = 10\) in this case, then it is easy to see that \(p_1\) is either 3 or 11 as \(p_1-1\) should be a factor \(>1\) of 10. In any case, we miss the factor 5 on the left hand side. Thus \(n\) cannot be of the form \(p_1^{k_1}\). Clearly for \(n=1\), the equation is not satisfied. Hence no such \(n\) can exist.
Solution of Nagendra. The argument is similar to that of the above one. But the bound that is being used here is somewhat bigger and more powerful. Cases \(k=1\) and \(k=2\) can be proved on similar lines. However, for case \(k ≥3\), we use the following lemma which is stronger than the lemma presented in the previous solution.
Lemma If \(k ≥ 2\) and if \(p_1, p_2,...,p_k\) are distinct primes with the assumption that \(p_1 < p_2 < ... < p_k\), then
We leave the proof to the readers, with the hint that \(p_1p_2 < (p_1-1)(p_2-1)+p_2 \). This is quite simple.
Now, if there are at least three distinct primes factors for \(n\), then with the same convention as in lemma, we will be having, \(p_2 ≥ 3\) and \(p_3 ≥ 5\). Thus
This proves that, if at all \(n\) has more than three distinct prime factors, then it is obvious that \( n- φ(n)\) cannot be equal to 10.
No comments:
Post a Comment