Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
1  
Where did you get this from? –  chubakueno Dec 28 '13 at 6:24

3 Answers 3

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

share|improve this answer
    
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).$$

share|improve this answer
2  
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
1  
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

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$

share|improve this answer
2  
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
2  
@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
2  
@Laplacian: In what sense does Fermat's theorem break down when $n \ge 2p$? –  Erick Wong Dec 29 '13 at 4:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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