1
$\begingroup$

Prove that if $a$ and $b$ are positive integers and $$(4ab-1) \mid (4a^2-1)$$ then $a=b$.

I am stuck with question, no idea. Is there any way to prove this using Polynomial Division Algorithm? Would appreciate any help.

$\endgroup$
  • $\begingroup$ This actually holds even with the weaker assumption that $ 4ab - 1 \mid (4a^2 - 1)^2 $. $\endgroup$ – George V. Williams Apr 15 '15 at 19:48
  • $\begingroup$ I added a generalization to my answer which makes it crystal clear how this is nothing but the uniqueness of inverses. $\endgroup$ – Bill Dubuque Apr 15 '15 at 22:02
6
$\begingroup$

Note that $4ab\equiv 1\pmod {4ab-1}$ and if $4ab-1\mid 4a^2-1$ then $4a^2\equiv 1\pmod{4ab-1}$. So $$b\equiv (4a^2)b=a(4ab) \equiv a\pmod{4ab-1}.$$

Is that possible if $a\neq b$?

Without using modular arithmetic, you can write this as:

$$a-b = b(4a^2-1)-a(4ab-1) $$

So $4ab-1\mid a-b$.

$\endgroup$
  • $\begingroup$ The proof is just a special case of the uniqueness of inverses - see my answer. $\endgroup$ – Bill Dubuque Apr 15 '15 at 20:01
  • $\begingroup$ Well, yes, but you still arrive at $4ab-1\mid a-b$. @BillDubuque $\endgroup$ – Thomas Andrews Apr 15 '15 at 20:05
  • $\begingroup$ The point is that viewing it this way makes everything obvious, even the requisite inequality (omitted in your answer). I expanded my remark to emphasize this - giving the natural generalization of the OP's theorem. Hopefully that makes my point clearer. $\endgroup$ – Bill Dubuque Apr 15 '15 at 21:57
3
$\begingroup$

Clearly, $a \geq b$, since we need $4a^2-1 \geq 4ab-1$. We have $$\dfrac{4a^2-1}{4ab-1} = k \in \mathbb{Z}$$ Hence, $$k = \dfrac{4a^2-1}{4ab-1} = \dfrac{4a^2-4ab+4ab-1}{4ab-1} = 1 + \dfrac{4b(a-b)}{4ab-1}$$ Now note that $\gcd(4ab-1,4b)=1$, since $(4b)a - (4ab-1) = 1$. Hence, $4ab-1$ divides $a-b$. However $0 \leq a-b < 4ab-1$. Hence, $a-b=0 \implies a=b$.

$\endgroup$
3
$\begingroup$

Note $\,\ {\rm mod}\,\ 4ab\!-\!1\!:\,\ \overbrace{(4a)\color{#c00}a\equiv 1\equiv(4a)\color{#c00}b}^{\ \ \ \large \color{#c00}a\, \equiv\, (4a)^{-1}\equiv\,\color{#c00} b}\,\Rightarrow\, \color{#c00}{a\equiv b}\ $ by uniqueness of inverses (of $\,4a\,$ here)


Remark $\ $ For completeness, here is the standard proof of uniqueness of inverses:

$$\ ca\equiv 1\equiv cb \,\Rightarrow\, a\equiv a(cb)\equiv (ac)b\equiv b\quad\ \ $$

The OP Theorem becomes obvious when expressed in this general form, amounting simply to the uniqueness of inverses mod $\,n\,$ within the standard rep system $\,\{0,1,\ldots,n\!-\!1\},\,$ namely

Theorem $\ $ If $\, \color{#0a0}{a< bc}\, $ and $\, bc\!-\!1\mid ac\!-\!1\ $ then $\ a = b,\ $ for integers $\,a,b,c > 0$

Proof $\ \ {\rm mod}\,\ n\!=\!bc\!-\!1\!:\,\ bc\equiv 1\equiv ac\,\Rightarrow\, a\equiv c^{-1}\!\equiv b.\ $ $\,bc\!-\!1\mid ac\!-\!1\,\Rightarrow\, b\le a \le \color{#0a0}{bc\!-\!2}\,$ (by $\,b\not\equiv 0).\,$ So $\,a\equiv b\pmod{n}\,$ and $\,a,b\in \{0,1,\ldots,\color{#0a0}{n\!-\!1}\}\Rightarrow\, a=b\,$ (else $\,n\,$ divides the smaller natural $\,a\!-\!b> 0,\,$ contradiction). $\ \ $ QED

The OP is the special case $\ c = 4a,\ $ where $\ a < 4ab = bc,\,$ so the Theorem applies.

Note how translating the theorem into the language of congruences has simplified it so much that we immediately recognize it as a special case of a well-known result about uniqueness of inverses. This is yet another example of a ubiquitous principle that I frequently emphasize here, namely uniqueness theorems provide powerful tools for proving equalities.

$\endgroup$
1
$\begingroup$

Note that any integer $m \ge 2$ will do, instead of 4.

For example, take Thomas Andrew's solution, and put $m$ for $4$ everywhere:

Note that $mab\equiv 1\pmod {mab-1}$ and if $mab-1\mid ma^2-1$ then $ma^2\equiv 1\pmod{mab-1}$. So $$b\equiv (ma^2)b=a(mab) \equiv a\pmod{mab-1}.$$

Is that possible if $a\neq b$?

Without using modular arithmetic, you can write this as:

$$a-b = b(ma^2-1)-a(mab-1) $$

So $mab-1\mid a-b$.

My note:

To show that $mab-1 > a-b$ for $m \ge 2$, $ab-a+b-1 =(a+1)(b-1) \ge 0 $.

Note that if $m=b=1$, then $mab-1 = a-1$.

$\endgroup$
  • $\begingroup$ Yes: $\ (ma)a\equiv 1\equiv (ma)b\,\Rightarrow\, a\equiv (ma)^{-1}\equiv b\,$ by uniqueness of inverses, see my answer. To get the general result replace $\,ma\,$ by $\,c\,$ above. $\endgroup$ – Bill Dubuque Apr 15 '15 at 20:23
  • $\begingroup$ Update: even the inequality has a natural interpretation when viewed from this standpoint: it is simply what's needed for the inverses to lie in the standard rep range. So the theorem is precisely equivalent to the uniqueness of inverses in the standard rep range, except the congruence language has been removed, being replaced by equivalent divisibility language, which obscures the essence of the matter: inverse unqueness (and it is further obfuscated by choice of a specific modulus). See the edit to my remark.for details. $\endgroup$ – Bill Dubuque Apr 16 '15 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.