# Sum of $m\leq 300$ such that if $2013m$ divides $n^{n}-1$, then $2013m$ also divides $n-1$

Find the sum of all the integers $m$ with $1≤m≤300$ such that for any integer $n$ with $n≥2$, if $2013m$ divides $n^{n}-1$, then $2013m$ also divides $n-1$.

Unfortunately I cannot think of anything to do with this problem. Could somebody please tell me what to do? Any help would be truly appreciated.

Based on Googling, this was problem 22 from the 2013 Fall Online Math Open. See http://internetolympiad.org/archive/OMOFall13/OMOFall13Probs.pdf

The solutions are also online at http://internetolympiad.org/pages/15-omo_problems. The corresponding solution is repeated below.

We call an integer $M$ stable if $n^n = 1$ mod $M$ implies $n = 1$ mod $M$.

Lemma: $M$ is stable if for every prime $p | M$, every prime factor $q$ of $p-1$ also divides $M$.

Proof: Suppose $n^n = 1$ mod $M$. Showing $n = 1$ mod $M$ is equivalent to showing $n = 1$ mod $p^k$ for each $p^k | M$ (can show with Chinese Remainder Theorem if you want.) From $n^n = 1$ mod $M$ we get $\gcd(n, M) = 1$. Let $u | \phi(p^k)$ be the order of $n$ mod $p^k$. Since $n^n = 1$ mod $p^k$ we have $u | n$. Since $\phi(p^k) = p^{k-1}(p-1)$ and every $q | p-1$ divides $M$, $\gcd(n, \phi(p^k) = 1$. As defined, $u | n$ and $u | \phi(p^k)$, so $u = 1$, giving $n = 1$ mod $p^k. \,\,\square$

The problem is to find the sum of $m$ such that $2013m = 3 \cdot 11 \cdot 61 \cdot m$ is stable. By the stability lemma, $2 | 2013m$, $3 | 2013m$, $5|2013m$. Leaving aside the prime factors of $m$ for now, this forces $m$ to be a multiple of $10$.

At this point, check every such multiple up to $300$ for stability. The only potential sources of trickiness come from $10p$ for primes $p \le 30$, and finalizing these cases is straightforward.

primes = $2,3,5,7,11,13,17,19,23,29$, have to check prime factors of $1,2,4,6,10,12,16,18,22,28$ respectively. All of these are guaranteed to be in $2013 \cdot 10p$, except for $p = 29$, since $2013 \cdot 10 \cdot 29$ has no factor of 7.

Thus, the answer is $10 + 20 + \cdots + 280 + 300 = 4360$.

• Thanks a lot Sir. Sir, just out of curiosity, would it be possible for you to share with me some of the hardest problems (with numeric answers) you've seen (preferably on Number Theory, Algebraic Geometry or on Combinatorics)?I hope I'm not asking for too much, Sir. – Ishan May 31 '15 at 9:24