3
$\begingroup$

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.

  • 0
    You mean 'biggest' instead of 'least', no?2012-10-03
  • 0
    Re berci, you are right.2012-10-03

3 Answers 3

3

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$

  • 0
    $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.2012-10-03
  • 0
    @barto, when we know $8|(a+b)$ is it tough to identify $2$ as the smallest?2012-10-03
  • 0
    @bhattacharjee, indeed. That means $8$ is the only possible value.2012-10-03
  • 0
    @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.2012-10-03
  • 0
    @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.2012-10-03
  • 0
    Sorry, that was my fault, I mean the GREATEST possible value of p.2012-10-03
  • 0
    @ lab bhattacharjee: How do you find those pairs of a, b?2012-10-03
  • 0
    @jasoncube, I've added the explanation in the answer.2012-10-03
  • 0
    @labbhattacharjee Aren't we missing $a = 16A + 11$ and $b = 16B + 13$ (or equivalently, $b = 16B - 3$)? In this case $a + b = 16(A + B) + 8$, so we get the same result.2012-10-03
  • 0
    @RichardSullivan, agreed. I've missed $16A+11$ or $16C-5$ for the ease of calculation. Now $(-5)^3=-125\equiv 3\implies b\equiv -3$. Thanks.2012-10-03
1

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.

0

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$

  • 0
    @jasoncube, could you please have look into this generalized & simpler(?) answer, unless you've already one?2012-10-04