Science:Math Exam Resources/Courses/MATH312/December 2010/Question 05/Solution 1

We begin by noting that

$2\cdot 11=22=\varphi (n)=n\prod _{p\mid n}(1-\frac{1}{p})=n\prod _{p\mid n}\frac{p-1}{p}=\prod _{p_i^{{\alpha }_i}\parallel n}{p}_i^{{\alpha }_i-1}(p-1)$

where above we used the Fundamental Theorem of Arithmetic to write (recall that $\parallel$ means fully divides)

$n=\prod _{p_i^{{\alpha }_i}\parallel n}{p}_i^{{\alpha }_i}.$

Our main equation of discussion will be

$2\cdot 11=\prod _{p_i^{{\alpha }_i}\parallel n}{p}_i^{{\alpha }_i-1}(p_i-1)$.

We proceed in cases. First we discuss the powers of 2 in n.

Case 1: $8\mid n$. In this case, notice that 4 divides the right hand side of the main equation but only 2 divides the left hand side. This is a contradiction.

Case 2: $4\parallel n$. In this case, notice that 2 divides the right hand side of the main equation and 2 divides the left hand side. However, if another odd prime divides n, then the right hand side is divisible by an extra power of 2 which is a contradiction. The remaining subcase in this case is if no odd primes divde n, that is, $n=4$. But since also $\varphi (4)=2\ne 22$ this case cannot occur.

Case 3: $2\parallel n$ or n is odd . In either of these cases, since $\varphi$ is multiplicative and as $\varphi (2)=1$, we have that either of these cases can occur, that is, if $\varphi (n)=22$, then $\varphi (2n)=22.$ Therefore, without loss of generality, we suppose 2 does not divide $n$.

Now we deal with the odd primes. Notice that for each odd prime, we get a factor of 2 on the right hand side of the main equation. Thus only exactly one odd prime can occur. Thus $n=p^{\alpha }$. Since only 2 and 11 occur as prime factors on the left hand side of the equation, we know that we must have that $\alpha \le 2$ (the right hand side of the main equation has an $p^{\alpha -1}$ term so the factor could be 2). If $\alpha =2$, then the prime p in question must be 11 since p divides the right hand side. So $n=11^2$ but this is inadmissable since $\varphi (11^2)\ne 22$. Thus n is a prime. For primes, we have that $\varphi (p)=p-1$. This value we know is 22 and so $n=23$.

Thus combining the two discussions shows us that either $n=23$ or $n=46$ completing the question.