# g.c.d.{$m^p-m:m=2$ to $n$} $= ?$

Let $p$ be an odd prime and $n>2$ is an integer , then what is the $g.c.d.$ of the numbers
{$m^p-m:m=2$ to $n$} ? (by Fermat's little theorem it is easy to see , $2p$ divides the g.c.d. , but I can not proceed further)

-
Where did you get this from? – chubakueno Dec 28 '13 at 6:24

Let me expand on benh's answer, which somewhat answers the question for sufficiently large $m$. In particular, we have an exact answer when we set $m\geq \lceil \sqrt p\rceil$. I have yet to consider the case when $n>\lceil \sqrt p\rceil$, although it should be similar.

Let $D$ be the GCD that we seek.

Our first goal is reduce the types of $m$ we need to test.

1. It suffices to consider $m^p-m$ for prime $m$

Suppose we have $q$ any prime and $n$ any integer such that $$D|q^p-q$$ $$D|n^p-n$$ Then \begin{align*} (qn)^p-(qn) &= q^p(n^p)-q^p(n)+q^p(n)-(qn)\\ &=q^p(n^p-n)+n(q^p-q) \end{align*} Since $D$ divides $n^p-n$ and $q^p-q$, $D$ divides $q^p(n^p-n)+n(q^p-q)=(qn)^p-(qn)$.

This shows that it suffices to compute $D$ from all $m$ that are prime. Let us denote $$S_B=\{p\leq B\;|\;p\text{ is prime}\}$$

2. $D$ is squarefree if $B=\lceil\sqrt{p}\rceil$

Let $D$ be obtained from GCDs of $m^p-m$ with $m\in S_B$. Suppose we have some $q|D$. We are interested in whether $q^2|D$. Suppose it does, then we know that $$q^2|D, D|m^p-m$$ therefore $$q^2|m^p-m\Longleftrightarrow m^p-m\equiv 0\pmod{q^2}$$ However, suppose we have $q\in S_B$. Then when we test GCD with $m=q$, we have $$m^p-m=q^p-q=q^2q^{p-2}-q\equiv 0-q\equiv q^2-q\pmod{q^2}$$ which is not $0$. We restate this as follows:

$\textbf{Proposition.}$ Let $q\in S_B$ and let $D=\gcd(m^p-m\;|\;m\in S_B)$. Then $q^2\nmid D$.

From benh's answer, we know that for any $q|D$, we must have $$(q-1)|(p-1)$$ from which we can deduce $$q-1\leq \sqrt {p-1}$$ $$q\leq \sqrt {p-1}+1<\sqrt p + 1$$ $$q\leq \lceil \sqrt p\rceil$$

Therefore if we set $B=\lceil \sqrt p\rceil$, then any prime $q|D$ must lie in $S_B$. Now by our proposition above we must have $q^2\nmid D$. This shows that $D$ is squarefree.

3. Primes $l>p$ does not reduce $D$

Now we consider what happens when we take gcd of $D$ with some prime $l>\lceil \sqrt p\rceil$. Recall that we are not concerned with composite $>p$, since they are always divisible by $D$ by section 1. Suppose we have some integer $q$ such that $q|D$. Then since $D$ is squarefree, $q$ is in fact a prime.

We observe that \begin{align*} l^p-l &\equiv (l-q)^p-(l-q)\pmod {q}\\ &\equiv (l-2q)^p-(l-2q)\pmod {q}\\ &\dots\\ &\equiv (l-kq)^p-(l-kq)\pmod {q} \end{align*} So that $q|l^p-l$ if and only if $q|(l-kq)^p-(l-kq)$, i.e. when $m=l-kq$, for any integer $k$. But this means we can scale $m=l-kq$ such that $m\leq B$, which we then know that $q|m^p-m$.

Therefore in fact $q|l^p-l$ for any $l>\lceil \sqrt p\rceil$. By consider prime by prime, this shows that in fact $D|l^p-l$. Therefore $D$ does not change when taking GCD with $l>\lceil \sqrt p\rceil$.

4. Exact answer when $B=\lceil \sqrt p\rceil$

We summarize the results so far:
(1) We can find the minimum GCD $D$ by taking $B=\lceil \sqrt p\rceil$ and setting $$D=\gcd(m^p-m\;|\;m\in S_B)$$ taking GCD with larger $m$ does not change the result.

(2) Every prime factor $q$ of $D$ satisfies $$(q-1)|(p-1)$$ $$q^2\nmid D$$

Therefore, to find $D$, it suffices to consider all divisors of $p-1$: $$T=\{x\in\Bbb N\;|\; x|p-1\}$$ If $e\in T$ and $e+1$ is prime, then $e|D$. We can check this 1 by 1, through the list $T$.
(This is the same function as in benh's.)

5. Example

Let $p=7919$, the $1000$-th prime. We have the factorization $$p-1=2 \cdot 37 \cdot 107$$ so that our set $T$, integers that divide $p-1$, is $$T=\{1, 2, 37, 74, 107, 214, 3959, 7918\}$$ Note that $q-1\in T$, so we are interested in primes of $T+1$: $$T+1=\{2, 3, 38, 75, 108, 215, 3960, 7919\}$$ The primes are $$\{2,3,7191\}$$ Which tells us that $$D=2\cdot 3\cdot 7191=47514$$

A computer check tells us that this is correct, along with all other primes $\leq 7191$.

-
That's nice! So you found $D (=K_\infty(p))$. But why do we need result 3) for this? Isn't that clear from your 2) and the $(q-1)\mid (p-1)$-characterization being an equivalence? – benh Dec 30 '13 at 2:41
@benh Oh it appears to me that taking GCD with some prime $m>\lceil\sqrt p\rceil$ might result in 1 for some prime factors in $D$. My $D$ computation at (2) assumes that I only took GCD up till primes $\leq \lceil \sqrt p\rceil$. So now $D=K_{\infty}(p)=K_{B}(p)$ for $B\geq \lceil \sqrt p\rceil$. – Yong Hao Ng Dec 30 '13 at 6:54

I don't know whether you can easily obtain an exact result, but here is one about radicals:

Let $K_n(p) = \gcd \left(m^p-m | 2 \leq m\leq n\right)$ and $K_\infty(p) = \gcd(m^p-m | 2\leq m)$.

A prime number $q$ divides $K_\infty(p) \Leftrightarrow (q-1) \mid (p-1).$

This also shows $q \mid K_n(p)$ for all $2\leq n$.

proof:

If for any prime $q$ we have $(q-1) \mid (p-1)$, then also for $q\nmid m$ we have $m^{p-1} \equiv 1 \bmod q$. Thus $q\mid m^p-m$ for arbitrary $m$, showing $q \mid K_\infty (p)$.

Let $q$ divide $K_\infty(p)$. Then $m^{p-1}\equiv 1 \bmod q$ for arbitrary $2\leq m$ with $q\nmid m$. Hence, $p-1$ is a divided by the multiplicative order of $q$, that is $$\text{ord}(\Bbb Z / q\Bbb Z)^\times = q-1 \mid (p-1).$$

So you can give a closed form for the radical of $K_\infty(p)$: $$\text{rad}(K_\infty(p)) = \prod_{\substack{d \mid (p-1) \\ d+1 \;\text{prime}}}(d+1) \mid K_n(p).$$

-
By the way, I haven't found any number $p\leq 10000$ where $K_3(p) \neq K_\infty(p)$. – benh Dec 29 '13 at 3:51
Nice answer. Do you mean $2\leq n$ for line 4? – Yong Hao Ng Dec 29 '13 at 11:03
Yes, thank you! – benh Dec 29 '13 at 14:13
I have added an answer that expands upon your observation. The summary is the gcd is in fact squarefree when $n$ is taken to be $\lceil\sqrt p\rceil$ and therefore it reduces to your radical case. Also that it suffices to consider primes $m$ in $2\leq m\leq n$. Perhaps there can be an exact answer for specific $n$ too. – Yong Hao Ng Dec 29 '13 at 18:46

since $m^p-m=m(m^{p-1}-1)$ is an increasing sequence , so the require g.c.d. say $D \le 2^p-2$ .

Now let $q$ be a prime such that $q-1|p-1$ ; if $q|m$ then $q|m^p-m$ ; otherwise $q$ does

not divide $m$ , then by Fermatt's theorem , $m^{p-1}\equiv m^{q-1} \equiv 1(\mod q)$ , so $q|m^p-m$ so in any

case if $q$ is prime and $q-1|p-1$ then $q|m^p-m$ ; so if $q_1,...,q_r$ ' s are distinct primes such that

$q_i-1|p-1$ then $\prod_{i=1}^r q_i|D$ . Off-course this is not complete

-

There is only one case to consider i.e $n<2p$, otherwise,Fermat's theorem breaks down. Consider the first two consecutive terms of the set; from Fermat's theorem, $m^p-m=kp$ and $(m+1)^p-(m+1)=k'p$, divide the two equations to get; $(m^p-m)k'={(m+1)^p-(m+1)}k$, now either $(m^p-m)|{(m+1)^p-(m+1)} or$(m^p-m)|k$. Case 1:$(m^p-m)|{(m+1)^p-(m+1)}, it follows that $m(m^(p-1)-1)|(m+1){(m+1)^(p-1)-1}, now m does not divide m+1, else m=1, a contradiction, further, if${m^(p-1)-1}|{(m+1)^(p-1)-1}, then $m|(m+1)$, again a contradiction showing that case 1 does not hold afterall case 2: $(m^p-m)|k$ but since $(m^p-m)=kp$, it follows that either $k|(m^p-m)$ in which case k=1, or k is a multiple of (m^p-m) showing that $p=1$ a contradiction. the same argument follows for other consecutive values of the given set. Hence, the required $gcd=p$

-
Your answer looks very chaotic. I didn't read it all, but your final answer is certainly incorrect. Take for instance $n=3$ and $p=5$. The $\gcd$ will be divisible by $30$. – barto Dec 28 '13 at 10:48
@Laplacian: If you read my question you will see that I already know that $2p$ divides the required g.c.d. , hence your final answer that g.c.d.$=p$ can not be correct. – Souvik Dey Dec 28 '13 at 13:07
@Laplacian: In what sense does Fermat's theorem break down when $n \ge 2p$? – Erick Wong Dec 29 '13 at 4:40