For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also set $g(a,b):=0$ if $a=b$, and $g(a,b):=g(b,a)$ if $a<b$.) For a nonzero integer $m$ and a prime integer $p$, let $v_p(m)$ denote the maximum power $k\in\mathbb{N}\cup\{0\}$ such that $p^k$ divides $m$. The set $D(a,b)$ is given by $$D(a,b):=\big\{p\in\mathbb{N}\,\big|\,p\text{ is an odd prime and }p-1\mid a-b\big\}\,.$$ (a) Show that $$g(a,b)=\left\{\begin{array}{ll}1\,,&\text{if }b=0\text{ and }a\text{ is odd}\,, \\ 2\,,&\text{if }b>0\text{ and }a-b\text{ is odd}\,, \\ \displaystyle 2^{\min\big\{v_2(a-b)+2,b\big\}}\,\prod_{p\in D(a,b)}\,p^{\min\big\{v_p(a-b)+1,b\big\}}\,,&\text{if }a-b\text{ is even}\,.\end{array}\right.$$ (b) What is the minimum value $\ell(a,b)$ of $l\in\mathbb{N}\cup \{0\}$ such that there exists a subset $S\subseteq\mathbb{Z}$ of size $l$ for which $$g(a,b)=\underset{n\in S}{\gcd}\,\left(n^a-n^b\right)\,?$$ (With the convention $\gcd(\emptyset)=0$, we can say that $\ell(a,b)=0$ for $a=b$.)

For examples, $$g(a,0)=1$$ for all integers $a>0$, $$g(13,1)=2\cdot 3\cdot 5\cdot 7\cdot 13=2730\,,$$ and $$g(8,2)=2^{2}\cdot 3^2\cdot 7=252\,.$$ This post is inspired by Prove that $2730$ divides $n^{13} - n$ for all integers $n$.. Part (a) is known. Part (b) is still open, and is related to The GCD of a Univariate Integer-Valued Polynomial over a Set. We have the following bound: $$\ell(a,b)\leq a+1\,.$$ However, I believe that this inequality holds: $$\ell(a,b)\leq 2\,.$$

  • 1
    $\begingroup$ Part $(a)$ has something to do with the carmichael function, but I could not work out the details yet. $\endgroup$ – Peter Jul 5 '16 at 11:02
  • $\begingroup$ and did you get anywhere with this too? $\endgroup$ – samerivertwice Nov 13 '18 at 10:42
  • $\begingroup$ @RobertFrost Unfortunately, no, to both problems you asked about. $\endgroup$ – Batominovski Nov 13 '18 at 20:16

Your Answer

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

Browse other questions tagged or ask your own question.