Problem 1
Compute \(d(12000)\).
Solution
\(12000=2^5 \cdot 3 \cdot 5^3\), so \(d(12000)=d(2^5)d(3)d(5^3)=6\cdot 2 \cdot 4=48\)
Midterm Examination 3
Problem 2
Compute \(\sigma(864)\).
Solution
\(864=2^5 \cdot 3^3\), so \(\sigma(864)=\sigma(2^5)\sigma(3^3)\). We have \(\sigma(2^5)=2^6-1=63\) and \(\sigma(3^3)=1+3+9+27=40\). Thus \(\sigma(864)=63 \cdot 40=2520\).
Problem 3
Compute \(\phi(360)\).
Solution
Note \(360=2^3 \cdot 3^2 \cdot 5\). Now \(\phi(2^3)=2^2(2-1)=4\), \(\phi(3^2)=3^1(3-1)=6\) and \(\phi(5)=5-1=4\). Thus \(\phi(360)=4 \cdot 6 \cdot 4 =96\).
Problem 4
Recall that a pair \((a,b)\) is an amicable pair if the sum of the proper divisors of \(a\) is equal to \(b\) and the sum of the proper divisors of \(b\) is equal to \(a\). Verify \((220, 284)\) is an amicable pair.
Solution
Note \(220=2^2 \cdot 5 \cdot 11\) and \(284 = 2^2 \cdot 71\). We have \[\sigma(220)=\sigma(2^2)\sigma(5)\sigma(11)=7 \cdot 6 \cdot 12=504\] and \[\sigma(284)=\sigma(2^2)\sigma(71)=7 \cdot 72=504.\] Thus \(\sigma(220)-220=284\) and \(\sigma(284)-284=220\) as desired.
Problem 5
Determine the least residue of \(13^{17}\) modulo \(60\).
Solution
Note that \(13\) is relatively prime to \(60\) and \(\phi(60)=16\). Thus \(13^{16} \equiv 1 \pmod{60}\) by Euler’s theorem. Thus \(13^{17} \equiv 13 \pmod{60}\).
Problem 6
List all the totatives modulo \(24\).
Solution
We find \(\{1,5,7,11,13,17,19,23\}\).
Problem 7
Prove that \[\sum_{k=0}^n p^k = \frac{p^{n+1}-1}{p-1}\] for all positive integers \(n\) and primes \(p\).
Solution
We proceed by induction on \(n\).
For the basis step \(n=1\) we check: \[\sum_{k=0}^1 p^k = 1+p = \frac{p^{1+1}-1}{p-1}\] as desired.
For the induction step, we assume the equation is true for \(n\) and consider the case of \(n+1\). We compute: \[\begin{align*} &\sum_{k=0}^{n+1} p^k \\ =&\sum_{k=0}^{n} p^k + p^{n+1}\\ =&\frac{p^{n+1}-1}{p-1} + p^{n+1}\\ =&\frac{p^{n+1}-1 + p^{n+2}-p^{n+1}}{p-1}\\ =&\frac{p^{n+2}-1}{p-1} \end{align*}\] as desired.
Alternative solution: Let \(m=\sum_{k=0}^n p^k\). Then \[(p-1)m=\left(\sum_{k=1}^{n+1} p^{k}\right) - \left( \sum_{k=0}^n p^k \right) =p^{n+1}-1\] Since \(p \ne 1\), we divide to obtain \(m=(p^{n+1}-1)/(p-1)\) as desired.
Problem 8
Determine all positive integers \(n\) such that \(\phi(n)\) is prime.
Solution
Suppose \(\phi(n)\) is prime. Let \(n=p_1^{k_1}\cdots p_r^{k_r}\) be the prime-power decomposition of \(n\). Then \(\phi(n)=\phi(p_1^{k_1})\cdots \phi(p_r^{k_r})\) is prime. Thus each \(\phi(p^k)\) is either \(1\) or prime for each prime-power.
First, note that \(\phi(p^k)=1\) if and only if \(p^{k-1}(p-1)=1\). This is only possible when \(k=1\) and \(p=2\); in other words, \(p^k=2\).
Now consider the case where \(\phi(p^k)\) is a prime. Thus \(p^{k-1}(p-1)\) is prime. Thus, either \(p^{k-1}=1\) or \(p-1=1\). In the first case, \(k=1\) and \(p-1\) is prime; which is only possible if \(p=3\). In the second case \(p=2\) and \(p^{k-1}\) must be prime; thus \(k=2\). Thus, when \(\phi(p^k)\) is a prime power only when \(p^k=3\) or \(p^k=4\).
Thus, \(\phi(n)\) is a prime when \(n\) is \(3\), \(4\) or \(6\).
Observation: Many students wrote down \(\phi(n)\) for low values of \(n\). This is an excellent idea to see what the answer might be and also why.