I find this interesting question in a number theory book.

Given two positive integers $a, b$ such that $a>1, b>1, \gcd(a, b)=1$. Prove that there exists a positive integer $s$ such that $s(ab-1)^n + 1$ is a composite number $\forall n \in \mathbb{N}.$

Its solution is short but beautiful :)

  • $\begingroup$ $$s\equiv(-1)^{n+1}\pmod{ab}\implies s(ab-1)^n\equiv-1\pmod{ab}$$ $\endgroup$ – lab bhattacharjee Jul 23 '14 at 16:34
  • $\begingroup$ @labbhattacharjee, it says for all $n \in \mathbb{N}.$ $\endgroup$ – Ehsan M. Kermani Jul 23 '14 at 16:37
  • $\begingroup$ @primitiveroot, Can you please certify Ehsan's statement? $\endgroup$ – lab bhattacharjee Jul 23 '14 at 16:40
  • $\begingroup$ @labbhattacharjee You have to choose $s$ as a constant, it can't be dependent on n. $\endgroup$ – primitiveroot Jul 23 '14 at 16:43

Hint $\,\ c\mid 1\!+\!(\overbrace{c\!-\!1}^{\Large s})(\overbrace{c\!+\!1}^{\large ab-1})^n$

Derivation $\ $ Suppose $\ c\mid 1\!+\!st^n\,$ for all $\ n\ge 0.\,$ $\ n=0\,\Rightarrow\, c\mid 1\!+\!s,\,$ so $\,s = jc\!-\!1,\,$ some $\,j\in\Bbb Z.\,$ $\,{\rm mod}\ c\!:\,\ {\rm for\ \ all}\ \ n\!:\,\ 0\,\equiv\, 1\!+\!st^n\equiv 1\!-t^n\!\! \iff\! t^n\equiv 1\!\!\!\overset{\ \ \large n=1}\iff\!t\equiv 1\!\iff\! t= kc\!+\!1,\,$ some $\,k\in\Bbb Z.\,$ Therefore for all $\,n\!:\ c\mid 1+st^n\! \iff\! 1\!+\!st^n = 1\!+\!(jc\!-\!1)(kc\!+\!1)^n\ $ for integers $\,j,k.\phantom{I^{I^{I^I}}}$


Bill's hint is more than enough and kills it beautifully, but as another solution, let $p$ be a prime divisor of $ab-2$ and take $s = (p-1)!.$ By Wilson's theorem, we'd have

$$(p-1)!(ab-1)^n + 1 \equiv (-1)(1)^n + 1 \equiv 0 \;\; (\text{mod} \; p)$$

P.S. Coprime condition is redundant.


If $s=ab-3$ then

$$s(ab-1)^n+1\equiv -1(1)^n+1\equiv 0\pmod{ab-2}$$

Hence $(ab-2)|s(ab-1)^n+1$.

Since $a>1$ and $b>1$ and $\gcd(a,b)=1$, we have $ab-3\ge 3>1$. Hence $$ab-2<(ab-3)(ab-1)+1$$

Noting that $ab-2>1$ we have that $s(ab-1)^n+1$ is composite for all $n\in\mathbb{N}$ since it is divisible by but not equal to $ab-2$.

  • $\begingroup$ Same as my hint, i.e. $\ c+1 = ab-1 \,\Rightarrow\, s = c-1 = ab-3\ \ $ $\endgroup$ – Bill Dubuque Jul 23 '14 at 17:10
  • $\begingroup$ @BillDubuque I agree - I started my answer before you gave your hint though and was loathe to throw it out. Additionally this answer deals with a couple technicalities which the hint (naturally) doesn't cover. $\endgroup$ – Peter Woolfitt Jul 23 '14 at 17:11

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.