Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

I have no idea how to solve this. Please help. Thank you.

share|cite|improve this question
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
up vote 3 down vote accepted

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$

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

share|cite|improve this answer

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$

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

Your Answer


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.