Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

3 Answers

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|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
show 5 more comments

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|improve this answer
add comment

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|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
add comment

Your Answer

 
discard

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.