Mock AIME II 2012 Problems/Problem 14

Problem

Call a number a $\textit{near Carmichael number}$ if for all prime divisors $p$ of the $\textit{near Carmichael number}$ , $n$ , $(p-1)$ divides $(n-1)$ and $n$ is not prime. Find the sum of all two digit $\textit{near Carmichael numbers}$ .

Solution

Remark that all numbers of the form $2^n, 3^n, 5^n, 7^n$ for $n\ge 2$ are $\textit{near Carmichael numbers}$ . The proof of this is noting that $(a+1)^n-1\equiv 0\pmod{a}$ , which is proven by noting that $(a+1)^n\pmod{a}\equiv 1^n\pmod{a}$ , and therefore we get $1-1\equiv 0\pmod{a}$ . Therefore, some two digit $\textit{near Carmichael numbers}$ that we get are $16, 25, 27, 32, 49, 64, 81$ .

Now, we look for $\textit{near Carmichael numbers}$ of the form $n=2^a*3^b*5^c*7^d$ . Note that this means that $2|(n-1)$ , which is impossible, so we can’t have $2$ and $3$ together. Also, this implies that $4|(n-1)$ and $7|(n-1)$ , so we can’t have $2$ times any other prime to give us a $\textit{near Carmichael number}$ . We now look at numbers of the form $3^b*5^c*7^d$ . We can’t have $3$ and $7$ together because this would imply that $6$ divides $n-1$ , but $n-1\equiv 2\pmod3$ , so this is impossible. Hence, we look for numbers of the form $3^b*5^c$ and $5^c*7^d$ . The first case gives us $4|(3^b*5^c-1)$ or $4|((-1)^b*1-1)$ . Therefore $b\equiv 0\pmod 2$ , which gives us $b=2, 4$ . However, $b=4$ gives us no values for $c$ , therefore we must have $b=2$ and this gives us $c=1$ to give another $\textit{near Carmichael number}$ : $45$

Now, looking at the form $5^c*7^d$ gives us $4|(5^c*7^d-1)$ or $4|((-1)^d-1)$ or $d\equiv 0\pmod 2$ . Therefore $d=2$ , but this gives us no possibilities for $c$ that are greater than $0$ (which don’t fall into the first case), therefore there are none of this form.

Lastly, look at the form $m^n*b$ where $m$ is a one digit prime and $b$ is a two digit prime. Start out by looking at $2^n*b$ . For reasons explained before, this cannot be a $\textit{near Carmichael number}$ if $b$ is a two digit prime number. Now, look at numbers of the form $3^n*b$ . Since $(3-1)|(3^n*b-1)$ , we are going to need for $(b-1)|(3^n*b-1)$ . Therefore $3^n\equiv 1\pmod{b-1}$ . $n=1$ gives $b=3$ which isn’t a two digit prime number, $n=2$ gives $8\equiv 0\pmod{b-1}$ which gives a largest value of $b$ as $9$ . $n=3$ gives us $26\equiv 0\pmod{b-1}$ , therefore $b-1=13, 26$ or $b=14, 27$ which aren’t prime. $n=4$ gives us no two digit $\textit{near Carmichael numbers}$ , since $81*b$ for $b\ge 10$ is greater than $100$ .

Now, look at the form $5^n*b$ to note that either $n=1$ or $n=2$ . The first case gives us $5b$ and the second gives us $25b$ , which implies that $b<4$ which isn’t a two digit prime number. Therefore, we look at the first case. We need for $4|(5b-1)$ or $4|(b-1)$ . We also need $(b-1)|(5b-1)$ or $4\equiv 0\pmod{b}$ . However, this gives us $b\le 4$ , which gives us no two digit numbers that work.

Lastly, look at numbers of the form $7^n*b$ . Since $n=2$ implies that $b\le 2$ which isn’t a two digit prime number, we must have $n=1$ , and therefore we get numbers of the form $7b$ . Note that $b\le 14$ therefore $b=11$ or $13$ . The first one gives $6|76$ and $10|76$ both false, and the second one gives $6|90$ and $12|90$ , which the second one isn’t true.

Therefore, we have found our $\textit{near Carmichael numbers}$ to be $16, 25, 27, 32, 45, 49, 64, 81$ which gives us a sum of $\boxed{339}$ .

Page

Toolbox

Search

Mock AIME II 2012 Problems/Problem 14

Problem

Solution