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

We begin by noting that

$\displaystyle 2\cdot 11=22=\phi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)=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 $\displaystyle \parallel$ means fully divides)

$\displaystyle n=\prod _{p_{i}^{\alpha _{i}}\parallel n}p_{i}^{\alpha _{i}}.$

Our main equation of discussion will be

$\displaystyle 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: $\displaystyle 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: $\displaystyle 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, $\displaystyle n=4$. But since also $\displaystyle \phi (4)=2\neq 22$ this case cannot occur.

Case 3: $\displaystyle 2\parallel n$ or n is odd . In either of these cases, since $\displaystyle \phi$ is multiplicative and as $\displaystyle \phi (2)=1$, we have that either of these cases can occur, that is, if $\displaystyle \phi (n)=22$, then $\displaystyle \phi (2n)=22.$ Therefore, without loss of generality, we suppose 2 does not divide $\displaystyle 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 $\displaystyle 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 $\displaystyle \alpha \leq 2$ (the right hand side of the main equation has an $\displaystyle p^{\alpha -1}$ term so the factor could be 2). If $\displaystyle \alpha =2$, then the prime p in question must be 11 since p divides the right hand side. So $\displaystyle n=11^{2}$ but this is inadmissable since $\displaystyle \phi (11^{2})\neq 22$. Thus n is a prime. For primes, we have that $\displaystyle \phi (p)=p-1$. This value we know is 22 and so $\displaystyle n=23$.

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