For any positive integers $a$, $b$, if $ab+1$ is a multiple of $16$, then $a+b$ must be a multiple of $p$. Find the largest possible value of $p$.

-
You mean 'biggest' instead of 'least', no? – Berci Oct 3 '12 at 10:46
Re berci, you are right. – ᴊ ᴀ s ᴏ ɴ Oct 3 '12 at 11:27

Observe that $(ab,16)=1$

If $a=16A+1,b=16B-1\implies a+b=16(A+B)$

If $a=16A+3,b=16B+5\implies a+b=16(A+B)+8$

If $a=16A+7,b=16B+9\implies a+b=16(A+B+1)$

So, in all the cases, $8\mid (a+b)$

As to find the pairs, as $ab\equiv -1\pmod {16}$ ,so $a(-b)\equiv 1$ i.e.,$-b$ is inverse of $a\pmod {16}$.

we know by this, $\lambda(16)=4\implies a^4\equiv 1\pmod {16}\implies a^{-1}\equiv a^3$

For example, $a=3,a^3=27\equiv -5\pmod {16}\implies b\equiv 5$

But $16$ is small enough to allow mental arithmetic, we just need to multiply $m,n$ where $m\le n<16$ and $(mn,16)=1$

-
$8$ is indeed the maximum value of $p$. No bigger value is possible, because $ab+1=16$ has $a+b=3+5=8$ as maximum. – barto Oct 3 '12 at 11:01
@barto, when we know $8|(a+b)$ is it tough to identify $2$ as the smallest? – lab bhattacharjee Oct 3 '12 at 11:03
@bhattacharjee, indeed. That means $8$ is the only possible value. – barto Oct 3 '12 at 11:10
@barto But as Berci points out, the OP is asking for the least possible value of $p$, which is clearly 1, or if $p$ is prime, 2. – Richard Sullivan Oct 3 '12 at 11:16
@barto How $8$ can be the only possible value? It can be $1,2,4$ also? Also, $(a+b)$ can be $16 (15+1 or 7+9), 32(31+1)$ etc. – Sumit Bhowmick Oct 3 '12 at 12:04

We can consider the problem in $\mathbb{Z}_{16}$.

Then $ab+1$ is a multiple of 16 means that $\overline{ab+1}=\overline{0}$, then $\overline{a}\overline{b}=\overline{ab}=\overline{15}$, in $\mathbb{Z}_{16}$, $\overline{15}$ only has four decompositions, means $\overline{15}=\overline{1}\cdot\overline{15}=\overline{3}\cdot\overline{5}=\overline{7}\cdot\overline{9}=\overline{11}\cdot\overline{13}$.

So $\overline{a+b}=\overline{a}+\overline{b}$ only has four cases, means $\overline{1}+\overline{15}=\overline{0}$, $\overline{3}+\overline{5}=\overline{8}$, $\overline{7}+\overline{9}=\overline{0}$ and $\overline{11}+\overline{13}=\overline{8}$.

So $\overline{a+b}=\overline{0}$ or $\overline{a+b}=\overline{8}$, $a+b$ must be a multiple of 8 (the case that $a+b$ is a multiple of 16 is include in this case), the least possible value of $p$ is 8.

-

Let $ab\equiv-1\pmod {2^k}$

If $a=1,b\equiv-1= c2^k-1,a+b=c2^k$, the minimum value of $c$ is $1$.

So, $p$ must divide $2^k$, so can not have any odd factor.

Now, $b\equiv -\frac 1 a\pmod {2^k}$ as $ab\equiv-1$

So, $b\equiv -\frac 1 a\pmod {2^t}$

Let $2^t||(a+b)$ clearly, $t\le k$

So,$a\equiv -b \pmod{2^t}\equiv \frac 1 a \implies a^2\equiv 1\pmod{2^t}$ as $(a,2)=1$

As $a$ is odd, $=2d+1$ (say), $a^2-1=8\frac{d(d+1)}2\implies 8\mid (a^2-1) ∀$ odd $a$.

Now $\frac{d(d+1)}2$ will be even if $4\mid d(d+1)\implies d=4e$ or $d+1=4e$ as $(d,d+1)=1$

So, $\frac{d(d+1)}2$ will be odd if $d=4e+1$ or if $d=4e+2$

If $d=4e+1,a=2d+1=8e+3,a^2-1=64e^2+48e+8=8(8e^2+6e+1)$

If $d=4e+2,a=2d+1=8e+5,a^2-1=64e^2+80e+24=8(8e^2+10e+3)$

In a more compact way,if $a=8e\pm 3, a^2-1=(8e\pm 3)^2-1=64e^2\pm48c+8=8(8c^2\pm6c+1)$

$\implies 2^3||(a^2-1)$ if $a\equiv 3,5\pmod 8$

$\implies p=8 ∀ k\ge 3$ as $k=2\implies a+b=4c$

-
@jasoncube, could you please have look into this generalized & simpler(?) answer, unless you've already one? – lab bhattacharjee Oct 4 '12 at 11:59