Maths Olympiad Prep

Library / /13 of 97

Number theory Difficulty 7.4 National olympiad, round 2 Find the answer

Find all positive integer m m if there exists prime number p p such that n m m\text{n m m} can not be divided by p p for any integer n n.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

We are asked to find all positive integers m m such that there exists a prime number p p for which nmm n^m - m is not divisible by p p for any integer n n .

We claim that the answer is all m1 m \neq 1 .

First, consider m=1 m = 1 . In this case, the expression becomes n1 n - 1 , which can clearly be a multiple of any prime p p by choosing n1(modp) n \equiv 1 \pmod{p} .

Now, consider m>1 m > 1 . Let p p be an arbitrary prime factor of m m . Write m=pkl m = p^k l , where gcd(l,p)=1 \gcd(l, p) = 1 . Assume that no prime q q exists such that nmm0(modq) n^m - m \equiv 0 \pmod{q} has no solution for n n .

Consider the expression (pkl)p1+(pkl)p2++pkl+1 (p^k l)^{p-1} + (p^k l)^{p-2} + \cdots + p^k l + 1 . Since the left-hand side is not congruent to 1(modpk+1) 1 \pmod{p^{k+1}} , we can choose q q such that q≢1(modpk+1) q \not\equiv 1 \pmod{p^{k+1}} . We will show that this q q leads to a contradiction.

First, note that the remainder of mp1+mp2++1 m^{p-1} + m^{p-2} + \cdots + 1 when divided by m1 m - 1 is p p , which is relatively prime to m1=pkl1 m - 1 = p^k l - 1 . Thus, gcd(q,m1)=1 \gcd(q, m - 1) = 1 , so m≢1(modq) m \not\equiv 1 \pmod{q} .

Since nmm(modq) n^m \equiv m \pmod{q} , we have npklpkl(modq) n^{p^k l} \equiv p^k l \pmod{q} , so npk+1l(pkl)p1(modq) n^{p^{k+1} l} \equiv (p^k l)^p \equiv 1 \pmod{q} . Let the order of n(modq) n \pmod{q} be x x . This means xpk+1l x \mid p^{k+1} l . However, since npklpkl(modq) n^{p^k l} \equiv p^k l \pmod{q} , which is not congruent to 1(modq) 1 \pmod{q} , we have that x x is not a factor of pkl p^k l , so pk+1x(q1) p^{k+1} \mid x \mid (q - 1) , implying q1(modpk+1) q \equiv 1 \pmod{p^{k+1}} , which is a contradiction.

Thus, there exists a prime q q such that q q is not a factor of nmm n^m - m for all integers n n .

The answer is: m\boxed{m \neq} 1}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.