# Prove that there exists $s$ such that $s(ab-1)^n +1$ is composite

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 :)

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

• Same as my hint, i.e. $\ c+1 = ab-1 \,\Rightarrow\, s = c-1 = ab-3\ \$ – Bill Dubuque Jul 23 '14 at 17:10
• @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. – Peter Woolfitt Jul 23 '14 at 17:11