0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ishan May 31 '15 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.