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