Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_II_2012_Problems/Problem_14&oldid=46161"