Does $a(a^{-1} \bmod b) + b(b^{-1} \bmod a) < ab + 2$ hold?

Question

Here we assume $(a,b) = 1$ and $a^{-1}$ and $b^{-1}$ are canonical (e.g. $0 < a^{-1} < b)$.

Counter example or proof are appreciated!

So you're assuming $a$ and $b$ are relatively prime (positive) integers here? — Ted Shifrin, Aug 30 '20 at 21:48
Hint: the $x$ and $y$ in $xa+yb=1$ (which are guaranteed by the definition of GCD) can both be taken to be in 'canonical' range $|x|\lt b$, $|y|\lt a$. — Steven Stadnicki, Aug 30 '20 at 21:53
Almost the right hint, but you need actual positive representatives. That is, the definition of "canonical" did not allow negative numbers. — Ted Shifrin, Aug 30 '20 at 21:54
@TedShifrin That's why it's a hint. :-) Finding positive representatives from that is a quick next step... — Steven Stadnicki, Aug 30 '20 at 21:55
It just confused me to use the word "canonical" two different ways, but of course I get it. — Ted Shifrin, Aug 30 '20 at 21:56

score 3 · Accepted Answer · answered Aug 30 '20 at 21:55

3

Hint. Let $x=a(a^{-1} \bmod b) + b(b^{-1} \bmod a) $. Then $x\equiv 1\pmod{ab}$ and $x<2ab$.

answered Aug 30 '20 at 21:55

Fabio Lucchini

16,054

Ted Shifrin · Answer 2 · 2020-08-30T22:10:34.400

1

HINT: If you use the Euclidean algorithm, you get integers $m,n$ with $ma+nb=1$. One will be positive, one will be negative. Without loss of generality, take $m<0<n$. Then how do you get your canonical $a^{-1}$ from $m$ and your canonical $b^{-1}$ from $n$?

By the way, now that you're done, it seems that the answer will always be $ab+1$. That follows from both suggested proofs.

edited Aug 30 '20 at 22:10

answered Aug 30 '20 at 21:56

Ted Shifrin

115,160

Does $a(a^{-1} \bmod b) + b(b^{-1} \bmod a) < ab + 2$ hold?

2 Answers2