Catalan Conjectures Reading Notes

Tags: #projects/notes/reading #projects/notes/seminars

Catalan

Website: https://www.daniellitt.com/ccam

Last Time

  • The Diophantine equation \(x^p-y^q = 1\) with \(p, q\geq 2\) has only one 4-tuple solution: \begin{align*} (\pm 3)^2 - 2^3 = 1 .\end{align*}

  • Used Mihăilescu’s work from 2000-2003 to take care of odd prime cases. Leaves some cases:

    • \(p=2\) with \(q\) arbitrary,
    • \(q=2\) with \(p\) arbitrary,
  • Reduced to elementary number theory!

Today

  • Today: the families \begin{align*} x^2 - y^q = 1 && x^p - y^2 = 1 .\end{align*}

  • Idea: prove

    • \(q=2\) and \(p\geq 2\) arbitrary,
    • \(p=2\) and \(q\geq 5\) arbitrary.
    • Next time: \(p=2, q=3\) in Chapter 4. Note \(x^2 = y^3+1\) is an elliptic curve! Find solutions using descent (Raemeon!)
  • Notation:

    • \({\operatorname{Ord}}_p(x)\): the \(p{\hbox{-}}\)adic valuation of \(x\).
    • \(R^2\) for \(R\) a ring: the set of squares in the ring (not the product!)
    • More generally: \(R^p\) for the set of \(p\)th powers

Preliminaries

In \(R\) a UFD, if \(\left\langle{a, b}\right\rangle = \left\langle{1}\right\rangle\) and \(ab = c^n \implies a = u_a r^n, b= u_b s^n\) for some units \(u_a, u_b\) and \(r,s \in R\).

Proof omitted, example has essential idea:

  • \(a = 2^8 3^4\),
  • \(b = 5^2 7^6\)
  • \(c^2 = ab\), so \(n=2\)

Then write \begin{align*} c^2 = ab = 2^8 3^4 5^2 7^6 = (2^4 3^2 5 7^3)^2 = (2^4 3^2)^2 (5 7^3)^2 \coloneqq r^2 s^2 .\end{align*}

Notes:

  • \(n\) had to divide every exponent

  • For this, need coprimality: \(n\) divided every exponent in the factorization of \(c^2\), but this can go wrong by just splitting up a power:

    • \(a= 2^8 3^4 5\)
    • \(b = 5 7^6\)

\(1+i\) divides \(a+bi\) in \({\mathbb{Z}}[i] \iff a,b\) have the same parity.

\envlist
  • Use that \(N(1+i) \divides N(\alpha) \iff (1+i)\divides \alpha\)
    • \(\impliedby\): Clear from properties of norm
    • \(\implies\): Expand \(a+bi = (1+i)(c + di)\) and solve a \(2\times 2\) system.
  • So \(2\divides a^2 + b^2\), forcing them to have the same parity.

Extend \begin{align*} {\operatorname{Ord}}_2:{\mathbb{Z}}&\to {\mathbb{Z}}_{\geq 0} \leadsto {\operatorname{Ord}}_2:{\mathbb{Q}}\to {\mathbb{Z}}_{\geq 0} \\ \\ {\operatorname{Ord}}_2(x/y) &= {\operatorname{Ord}}_2(x) - {\operatorname{Ord}}_2(y) \\ {\operatorname{Ord}}_2(0) &= \infty .\end{align*} Properties: \begin{align*} {\operatorname{Ord}}_2(xy)&= {\operatorname{Ord}}_2(x) + {\operatorname{Ord}}_2(y) \\ {\operatorname{Ord}}_2(x+y) &\geq \min({\operatorname{Ord}}_2(x), {\operatorname{Ord}}_2(y)) && \text{equality iff } {\operatorname{Ord}}_2(x) \neq {\operatorname{Ord}}_2(y) .\end{align*}

For \(q\) prime, \(x,y\in {\mathbb{Z}}\) distinct with \(\gcd(x, y) = 1\), \begin{align*} \gcd\qty{ {x^q - y^q \over x-y}, x-y } \divides q .\end{align*}

Note: useful because \begin{align*} x^q - y^q = (x-y)\qty{x^q - y^q \over x-y} .\end{align*}

Ch 2: \(q=2\)

\begin{align*} x^p - y^2 = 1 .\end{align*}

Projects/Talks In Progress/Catalan/figures/2021-09-10_01-16-59.png

Projects/Talks In Progress/Catalan/figures/2021-09-10_01-18-12.png

Projects/Talks In Progress/Catalan/figures/2021-09-10_01-18-33.png

  • Proof idea: a 2-adic argument, use properties of \({\mathbb{Z}}[i]\).

The Diophantine equation \begin{align*} x^p- y^2 = 1 \end{align*} has no solutions for \(p\geq 2\) and \(x, y\in {\mathbb{Z}}_{\neq 0}\).

Note: not Henri Lebesgue, of integral fame, late 1800s. Instead: Victor-Amédée Lebesgue, early 1880s. Simplified \(n=4,5,7\) cases of Fermat’s last theorem.

  • Take \(x, y\) nonzero solutions, so \(x^p = y^2 + 1\).

Can assume \(p\) is odd.

\envlist
  • If not, suppose \(p\) is even.

  • Factor \begin{align*} (x^{p\over 2} - y)(x^{p\over 2} + y) = 1 \implies x^{p\over 2} \pm y = 1 ,\end{align*} where they both have to have the same sign.

  • Subtract equations: \begin{align*} x^{p\over 2} + y &= \pm 1\\ x^{p\over 2} - y &= \pm 1 \\ \hline \\ y-(-y) &= 0 \implies 2y = 0 \implies y=0 ,\end{align*}

  • But we assumed \(y\neq 0\). \(\contradiction\)

\(x, y\) have opposite parity.

\envlist
  • Reduce \(\operatorname{mod}2\).
  • \(y\) even \(\implies y = 0 \operatorname{mod}2 \implies y^2 = 0\operatorname{mod}2 \implies x^p = y^2 + 1 = 1 \operatorname{mod}2 \implies x\) odd
  • \(y\) odd \(\implies y = 1 \operatorname{mod}2 \implies y^2 = 1\operatorname{mod}2 \implies x^p = y^2 + 1 = 1 + 1 = 2 = 0 \operatorname{mod}2 \implies x\) even.

\(y\) is even, \(x\) is odd.

\envlist
  • Consider \begin{align*} x^p = y^2 + 1 \operatorname{mod}4 .\end{align*}

  • Consider all squares in \({\mathbb{Z}}/4\): \begin{align*} {\mathbb{Z}}/4 = \left\{{0,1,2,3}\right\} &\implies ({\mathbb{Z}}/4)^2 = \left\{{0,1,4,9}\right\} = \left\{{0,1,0,1}\right\} = \left\{{0, 1}\right\} \\ &\implies y^2 = 0, 1\operatorname{mod}4 .\end{align*}

  • Toward a contradiction, suppose \(y\) is odd (implicitly: \(x\) is even)

  • \(y^2\) odd \(\implies y^2 = 1,3 \operatorname{mod}4 \implies y^2 = 1 \operatorname{mod}4\) since the only squares mod 4 are 0, 1.

  • Then \(x^p = y^2 + 1 = 2\operatorname{mod}4\).

  • \(x\) even \(\implies x^n = 0 \operatorname{mod}4\) for any \(n \geq 2\).

    • Why: \(x\) even \(\implies x=0, 2 \operatorname{mod}4 \implies x^2 = 0^2, 2^2 = 0 \operatorname{mod}4\), etc.
  • Now have \(x^p = 2\) and \(x^p = 0 \operatorname{mod}4\). \(\contradiction\)

\(\gcd(1+iy, 1-iy) = 1 \in {\mathbb{Z}}[i]\).

\envlist
  • Check that \(d\divides 1+iy \implies N(d) \divides 2\) so \(N(d) = \pm 1,2\).
  • \(N(d) = 1 \iff d\) is a unit
  • \(N(d) = 2 \iff a^2 + b^2 = 2 \implies a=b=1\)
  • \(1+i \notdivides 1 \pm i y\) since \(1, y\) have different parities, using that \(y\) is even.
  • Since \(p\) is odd, \(U({\mathbb{Z}}[i]) = \left\{{\pm 1, \pm i}\right\}\) are all \(p\)th powers:
    • \((\pm 1)^p = \pm 1\)
    • \(i^p = \pm i \implies (-i)^p = -i^p = \mp i\).
  • Factor \begin{align*} x^p = y^2 + 1 &= (1+iy)(1-iy) \in ({\mathbb{Z}}[i])^p .\end{align*}

Continuing the proof, use that \((1\pm iy)\) are coprime to apply UFD power lemma: \begin{align*} x^p = y^2 + 1 = (1+iy)(1-iy) &\in ({\mathbb{Z}}[i])^p \\ \implies 1 + iy &\in ({\mathbb{Z}}[i])^p && \text{by UFD lemma} \\ \implies 1 + iy &= c^p,\, \exists c\in {\mathbb{Z}}[i] .\end{align*}

\(c + \mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu = \pm 2\), and thus \(c = \pm(1 + bi) \in 1 + i{\mathbb{Z}}\).

Check \begin{align*} c^p + \mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu^p = c^p + \mkern 1.5mu\overline{\mkern-1.5muc^p\mkern-1.5mu}\mkern 1.5mu = (1+iy) + (1-iy) = 2 ,\end{align*}

  • Use that \begin{align*} z^n - w^n &= (z-w)\sum_{k=0}^{n-1} z^kw^{n-k} \\ &= (z^{n-1} + z^{n-2}w + \cdots + w^{n-1}) \\ \\ \implies z^n + w^n &= z^n - (-w)^n && \text{for $n$ odd} \\ &= (z+w)\sum_{k=0}^{n-1} z^k(-w)^{n-k} \\ &= (z^{n-1} - z^{n-2}w + \cdots + w^{n-1}) && \text{since $n-1$ is even} .\end{align*}

  • Take \(z= c^p, w=\mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu^p\): \begin{align*} 2 = c^p + \mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu^p &= (c+\mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu)(c^{p-1} - c^{p-2} \mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu + \cdots + \mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu^{p-1}) \\ \\ &\implies c+\mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu\divides 2 \in {\mathbb{Z}}\\ &\implies c+\mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu = \pm 2 \quad \text{ since } c + \mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu \text{ is even} .\end{align*}

  • Write \(c = b'+ bi, \mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu= b' - bi\), then \begin{align*} & \pm 2 = c + \mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu = 2b' \\ &\implies b' = \pm 1 \\ &\implies c = \pm(1 + bi) .\end{align*}

Since \(y\) is even, \(c = \pm(1 + bi)\) is not divisible by \(1+i\).

Now WTS: \((1+i) \notdivides c\).

  • Toward a contradiction: if so, \begin{align*} 1+i &\divides c \\ \implies 1+i &\divides c^p = 1 + iy \\ \iff 1 &\equiv y \operatorname{mod}2 && \text{by parity divisibility lemma}\\ \iff y &\text{ is odd} && \contradiction .\end{align*}

Now \begin{align*} y \text{ even } &\implies (1+i)\notdivides c = \pm(1 + bi) \\ &\iff 1 \not\equiv b \operatorname{mod}2 \quad \text{by parity divisibility lemma} \\ &\iff b \text{ is even} \\ &\implies c\in 1 + 2i{\mathbb{Z}} .\end{align*}

  • Now reduce \(\operatorname{mod}8\) to conclude that we take \(+2\) in the following equation: \begin{align*} \pm 2 = c^p + \mkern 1.5mu\overline{\mkern-1.5muc\mkern-1.5mu}\mkern 1.5mu^p &= (1+bi)^p + (1-bi)^p \\ \implies \pm 2 &\equiv (1+bi)^p + (1-bi)^p \operatorname{mod}8{\mathbb{Z}}[i] .\end{align*}

  • Take binomial expansion of this expression to find a relation among the binomial coefficients \({p\choose k}\): \begin{align*} {p \choose 2}(bi)^2 + {p\choose 4}(bi)^4 + \cdots + {p\choose p-1} (bi)^{p-1} = 0 .\end{align*}

The leading term has the (strictly) lowest 2-adic valuation: \begin{align*} S\coloneqq\sum s_k \coloneqq{\operatorname{Ord}}_2\qty{ {p\choose k}(bi)^k } > {\operatorname{Ord}}_2\qty{ {p\choose 2} (bi)^2 } ,\end{align*} also implying that all of the pairs \(({\operatorname{Ord}}_2(s_1), {\operatorname{Ord}}_2(s_k))\) are distinct. Thus \begin{align*} {\operatorname{Ord}}_2(S) = \min {\operatorname{Ord}}_2(s_k) = {\operatorname{Ord}}_2(s_1) \end{align*}

\envlist
  • Why this finishes the proof: use that \({\operatorname{Ord}}_2(a + b) \geq \min({\operatorname{Ord}}_2(a), {\operatorname{Ord}}_2(b))\) with equality when \({\operatorname{Ord}}_2(a)\neq {\operatorname{Ord}}_2(b)\) are distinct.

  • Note \(S=0\), now apply above repeatedly to \(s_1, s_k\) to get \begin{align*} {\operatorname{Ord}}_2(s_1) = {\operatorname{Ord}}_2(S) = {\operatorname{Ord}}_2(0) = 0\\ \implies {\operatorname{Ord}}_2\qty{ {p\choose 2} (bi)^2 } = {\operatorname{Ord}}_2\qty{{b^2p! \over 2(p-2)!} } = 0 \\ \implies b=0 \quad \text{since $b$ is even} ,\end{align*}

  • Then \begin{align*} c = 1+bi = 1+0i = 1 \\ \implies c=1 \\ \\ 1 = c^p = 1+iy \\ \implies y=0 .\end{align*}

  • This contradicts \(y\in {\mathbb{Z}}_{\neq 0}\) and finishes the entire proof.

\envlist
  • WTS: \({\operatorname{Ord}}(s_k/s_2) = {\operatorname{Ord}}(s_k) - {\operatorname{Ord}}(s_2) > 0\). \begin{align*} {\operatorname{Ord}}\qty{s_k\over s_2} &\coloneqq {\operatorname{Ord}}_2\qty{ {p\choose k} {p\choose 2}^{-1}(bi)^{k-2} }\\ &= {\operatorname{Ord}}_2\qty{ {p-2\choose k-2}\qty{2 (bi)^{k-2} \over k(k-1)} }\\ &= {\operatorname{Ord}}_2\qty{{p-2 \choose k-2}} + {\operatorname{Ord}}_2\qty{2(bi)^{k-2}} - {\operatorname{Ord}}_2(k(k-1)) \\ &> 0 ,\end{align*}

  • Use that

    • Binomial coefficients are integers \(\geq 1\)
    • \(b\) is even,
    • \(f(k) \coloneqq{\log(k) \over k-1}\searrow 0\), since \(f'(k) < 0\) everywhere,
    • \(f(2) = \log(2) \implies \log(2) > {\log k \over k- 1}\)
  • Then for any even \(k\geq 4\), \begin{align*} {\operatorname{Ord}}_2( 2(bi)^{k-2} ) &\geq k-1 \\ &{\color{red}>} {\log k \over \log 2} \\ &\geq {\operatorname{Ord}}_2(k) \\ &= {\operatorname{Ord}}_2(k(k-1)) \quad \text{since $k-1$ is odd}\\ \implies &{\operatorname{Ord}}_2(2(bi)^{k-2}) - {\operatorname{Ord}}_2(k(k-1)) > 0 .\end{align*}

Ch. 3: \(p=2\)

\begin{align*} x^2 - y^q = 1 .\end{align*} Projects/Talks In Progress/Catalan/figures/2021-09-10_01-14-53.png

Projects/Talks In Progress/Catalan/figures/2021-09-10_01-15-04.png

Projects/Talks In Progress/Catalan/figures/2021-09-10_01-15-14.png

Projects/Talks In Progress/Catalan/figures/2021-09-10_01-15-31.png

  • Proof due to Chao, 1965, adapted by Chein.

  • Idea: for \(q \geq 5\), we’ll show \(x^2-y^q=1\) has no solutions \(x, y\in {\mathbb{Z}}_{\neq 0}\).

    • Toward a contradiction, we’ll suppose such solutions exist.
    • Lemmas will give
      • \(x\equiv 0\operatorname{mod}q\)
      • \(x \equiv \pm 3 \operatorname{mod}q\)
    • But since \(q > 3\), this is absurd.

For \(q\geq 3 \in {\mathbb{Z}}\) an odd integer and \(x^2-y^q=1\), we have

  • For some coprime \(a, b\) with \(\gcd(2a, b) = 1\),
  • \(x-1 = 2^{q-1} a^q\)
  • \(x+1 = 2b^q\)
  • \(y=2ab\)
  • \(y\geq 2^{q-1}-2\).

Lemma 3.2

For \(q\geq 3 \in {\mathbb{Z}}\) an odd prime and \(x^2-y^q=1\) for \(x,y\in {\mathbb{Z}}_{\neq 0}\), \begin{align*} x\equiv 0 \operatorname{mod}q .\end{align*}

  • By contradiction: suppose \begin{align*} x^2 = y^q + 1 && x,y\neq 0, x\not\equiv 0 \operatorname{mod}q .\end{align*} We’ll contradict \(y\neq 0\).

  • Write \begin{align*} x^2 = y^q + 1 = (y+1)\qty{ y^q + 1 \over y+1} ,\end{align*} noting typo in book.

\begin{align*} d \coloneqq\gcd\qty{ y+1, \qty{ y^q + 1 \over y+1} } \implies d\divides q \implies d \in \left\{{1, q}\right\} .\end{align*}

  • Then \(d\divides x^2\) but \(x\not\equiv 0\operatorname{mod}q \implies d\neq q \implies d=1\).

\begin{align*} y+1, \qty{ y^q + 1 \over y+1} \in \pm1 \cdot {\mathbb{Z}}^2 .\end{align*}

\envlist
  • \(y^q + 1 = x^2 \in {\mathbb{Z}}^2 \implies y\geq 0\) using that \(q\) is odd.
    • If \(y\leq -1\) then \(y^q\leq -1 \implies y^q+1=x^2\leq -1, \contradiction\).
  • \(y\geq 0 \implies y+1 >0\) and \({y^q + 1\over y+1}>0\).
  • \(y+1>0\) and \(y+1\in \pm1 {\mathbb{Z}}^2 \implies y+1 \in +1{\mathbb{Z}}^2 \implies y+1 = u^2\) for some \(u\in {\mathbb{Z}}_{\neq 0}\).
  • Consider solutions to \begin{align*} f(X, Y) \coloneqq X^2 -yY^2 = 1 .\end{align*}
    • Contains \((u, 1)\) since \(u^2-y\cdot 1 = 1\)
    • Contains \((x, y^{q-1\over 2})\) since \(x^2 - y^q = 1\).
  • \(y\neq 0\implies y\geq 1\) is positive
  • \(y=u^2 -1 \geq 1\) is not a square (exercise) \(\implies f\) is a Pell equation:

x^2-ny^2=1 where n is a nonsquare

  • \(y\not\in {\mathbb{Z}}^2 \implies {\mathbb{Q}}[\sqrt y]/{\mathbb{Q}}\) is quadratic and \({\mathbb{Z}}[\sqrt y] \leq {\mathbb{Z}}_K\) is a subring of its ring of integers

    • Note: \(R \coloneqq{\mathbb{Z}}[\sqrt y]\) will be the ambient ring for the rest, with \({\mathbb{Z}}{\hbox{-}}\)basis \(\left\{{1, \sqrt y}\right\}\).
  • Exercise: \(U({\mathbb{Z}}[\sqrt y]) = \left\langle{-1. {\varepsilon}\coloneqq u + \sqrt y}\right\rangle\) are generators of its unit group, treat them as a \({\mathbb{Z}}{\hbox{-}}\)basis.

  • Thus \begin{align*} x + y^{q-1\over 2}\sqrt{y} = \pm(u + \sqrt y)^m,\quad \exists m\in {\mathbb{Z}} .\end{align*}

  • After possibly changing the sign of \(u\), we can assume \(m\geq 0\): \begin{align*} (u + \sqrt y) \cdot -(-u + \sqrt y) = -(u^2 + y) = u^2 - y = 1 \\ \implies (u + \sqrt y)^{-1}= -(-u + \sqrt y) .\end{align*}

  • Reduce equation mod \(y{\mathbb{Z}}[\sqrt y]\): \begin{align*} x + {\color{red} y^{q-1\over 2}\sqrt{y} } &\equiv \pm(u + \sqrt y)^m \operatorname{mod}yR \\ \implies x &\equiv \pm(u + \sqrt y)^m \operatorname{mod}yR \\ &\equiv \pm \sum_{k=0}^m {m\choose k}u^{m-k} (\sqrt y)^k \\ &\equiv \pm\qty{ u^m + {m\choose 1} u^{m-1}y^{1\over 2} + {m\choose 2}u^{m-2} y^1 + {\color{red} {m\choose 3}u^{m-3}y^{3\over 2} + \cdots} } \\ &\equiv \pm(u^m + mu^{m-1} y^{1\over 2}) \\ \implies x &\equiv \pm(u^m + mu^{m-1} \sqrt y) \operatorname{mod}yR .\end{align*}

  • Now equate coefficients: \begin{align*} mu^{m-1} \equiv 0 \operatorname{mod}yR \implies y\divides mu^{m-1} .\end{align*}

\(y\) is even and \(u\) is odd, since \(y+1 = u^2\).

  • Proof: omitted.
\envlist
  • Given this, since \(y \divides mu^{m-1}\) with \(y\) even and \(u\) odd, \(u^{\ell}\) is odd for all \(\ell\), so \(m\) must be even.

  • \(m\) even \(\implies\) this is legal: \begin{align*} x + y^{q-1\over 2}\sqrt y &= \pm (u + \sqrt y)^m \\ &= \pm\qty{\qty{u + \sqrt y}^2}^{m\over 2} \\ &= \pm \qty{u^2 + y + 2u\sqrt y }^{m\over 2} \\ \\ \implies x + y^{q-1\over 2}\sqrt y &\equiv \pm \qty{ {\color{red} u^2} + y + {\color{red} 2u\sqrt y} }^{m\over 2} \operatorname{mod}uR \\ &\equiv \pm y^{m\over 2} \\ \\ \implies x + y^{q-1\over 2}\sqrt y &\equiv \pm y^{m\over 2} + 0\sqrt y \operatorname{mod}uR \\ \implies u\divides y^{q-1\over 2} .\end{align*}

  • Now use \(y+1 = u^2 \implies d\coloneqq\gcd(u, y) = 1\)

    • Why: \(d\divides y\) and \(d\divides u\) implies \(d\divides u^2\) and \(d\divides u^2-y = 1\).
  • Then \(u\divides y^{q-1\over 2}\) and \(\gcd(u, y ) = 1 \implies u = \pm 1\).

  • Finish proof: \begin{align*} y+1 = u^2 = (\pm 1)^2 = 1 \implies y=0, \contradiction .\end{align*}

Lemma 3.3

For \(q\geq 3 \in {\mathbb{Z}}\) an odd prime and \(x^2-y^q=1\), \begin{align*} x\equiv \pm 3 \operatorname{mod}q .\end{align*}

  • Trivial if \(q=3\) since \(\pm 3 \equiv 0\operatorname{mod}3\) (applying previous lemma), so assume \(q\geq 5\).

Up to switching \(x\) and \(-x\),

\begin{align*} x-1 &= 2^{q-1} a^q\\ x+1 &= 2 b^q\\ y &= 2ab \\ \gcd(a, b) = 1 &= \gcd(2a, b) .\end{align*}

Proof omitted.

  • Use lemma to write \begin{align*} (b^q)^2 - (2a)^q &= \qty{x+1\over 2}^2 - 2(x-1) \\ &= \qty{x^2 + 2x +1 - 8(x-1)\over 4} \\ &= \qty{x-3\over 2}^2 .\end{align*}

  • Rewrite the LHS: \begin{align*} (b^q)^2 - (2a)^q = (b^2 - 2a)\qty{ (b^2)^q - (2a)^q \over b^2 - 2a } \coloneqq\alpha_1 \alpha_2 .\end{align*}

  • By the GCD \(q{\hbox{-}}\)division lemma (Exc. 3.2), \begin{align*} d\coloneqq\gcd( \alpha_1, \alpha_2)\divides q \implies d\in \left\{{1, q}\right\} .\end{align*}

\begin{align*} d=q .\end{align*}

Claim finishes the proof:

  • \(q\divides d \implies q\divides \alpha_1\) and \(q\divides \alpha_2\)
  • \(\implies q\divides \alpha_1 \alpha_2 = \qty{x-3\over 2}^2\)
  • \(\implies q\divides {x-3\over 2} \implies x\equiv 3 \operatorname{mod}q\).

Proof of claim that \(d=q\):

  • Know \(d\in \left\{{1, q}\right\}\) so toward a contradiction suppose \(d=1\) (we’ll contradict this)

  • Then \(\alpha_1 \alpha_2\in {\mathbb{Z}}^2\implies \alpha_1, \alpha_2 \in \pm {\mathbb{Z}}^2\) (by previous lemma)

  • Know \begin{align*} (b^2)^q - (2a)^q = \qty{x-3\over 2}^2 &\in +1\cdot {\mathbb{Z}}^2 \\ \implies (b^2)^q &\geq (2a)^q \\ \implies b^2 &\geq 2a \\ \implies \alpha_1, \alpha_2 &> 0 .\end{align*}

  • Also know \(\alpha_1 = b^2-2a \in +1 \cdot {\mathbb{Z}}\) is a positive square

  • \(y\neq 0, y=2ab \implies a\neq 0\).

  • Write \(b^2 - 2a = c^2\) where \(c^2\neq 0\) since \(a\neq 0\).

  • Now a contradiction: \({\left\lvert {a} \right\rvert}\geq {\left\lvert {b} \right\rvert}\) and \({\left\lvert {a} \right\rvert} < {\left\lvert {b} \right\rvert}\).

\begin{align*} {\left\lvert {a} \right\rvert} \geq {\left\lvert {b} \right\rvert} .\end{align*}

\envlist
  • Closest squares to \(b^2\) are \((b\pm 1)^2\), and \begin{align*} {\left\lvert {(b\pm 1)^2 - b^2} \right\rvert} &= {\left\lvert { b^2 \pm 2b + 1 - b^2} \right\rvert} \\ &= {\left\lvert { 1 \pm 2b} \right\rvert} \\ &\geq 2{\left\lvert {b} \right\rvert} - {\left\lvert {1} \right\rvert} .\end{align*}
  • Write \(c^2 = b^2 - 2a\), then since \((b\pm 1)\) is the closest square: \begin{align*} {\left\lvert {c^2 - b^2} \right\rvert} \geq {\left\lvert { (b\pm 1)^2 - b^2} \right\rvert}\geq 2{\left\lvert {b} \right\rvert} -1 \\ \implies {\left\lvert {c^2 - b^2} \right\rvert} = {\left\lvert { (b^2 - 2a) - b^2} \right\rvert} = {\left\lvert {2a} \right\rvert} \geq 2{\left\lvert {b} \right\rvert}-1 \\ \implies 2{\left\lvert {a} \right\rvert} \geq 2{\left\lvert {b} \right\rvert} - 1 \\ \implies {\left\lvert {a} \right\rvert} \geq {\left\lvert {b} \right\rvert} ,\end{align*} since we’re dealing with integers.

\begin{align*} {\left\lvert {a} \right\rvert} < {\left\lvert {b} \right\rvert} .\end{align*}

\envlist
  • Recall from lemma that \(x+1 = 2b^q\)
  • Use \(q\geq 5, q-1\geq 4, {\left\lvert {x} \right\rvert} \geq 2\) to write \begin{align*} {\left\lvert {a} \right\rvert}^q &= {{\left\lvert {x-1} \right\rvert} \over w^{q-1}} \\ &\leq {{\left\lvert {x-1} \right\rvert} \over 2^4} \\ &< {{\left\lvert {x-1} \right\rvert} \over 2} \\ &= {{\left\lvert {2b^q} \right\rvert} \over 2} \\ &= {\left\lvert {b} \right\rvert}^q ,\end{align*} then take \(q\)th roots.

This conclude the proof! \(\contradiction\).

#projects/notes/reading #projects/notes/seminars