In this article, we demonstrate a subtle but devastating backdoor in finite-field Diffie–Hellman. By computing public keys modulo $p^2$ instead of $p$ while restricting the secret exponent to $x \leq p-1$, the discrete logarithm becomes efficiently recoverable using Fermat quotients. We show the full derivation and provide a working Sage implementation. Backdoors are always bad — but they are catastrophic when they are embedded in a fundamental primitive like Diffie–Hellman key exchange. If your browser shows a green lock, you assume your connection is secure. But what if the implementation of Diffie–Hellman contains a tiny change that looks harmless in code review — and yet allows an attacker to recover the private exponent in milliseconds? In this post I’ll show a nasty little backdoor that requires only a tiny modification: using a modulus of $p^2$ instead of $p$, while keeping the secret exponent bounded by $p$ This ...
❚ I stumbled upon a really nice MO puzzle. No, that's is not a puzzle for my dog, who is also named MO, but a puzzle taken from the well known Mathematical Olympiad, which takes places once every year.
Proof
Before we distinguish two cases, let me first proof two facts which concerns special cases of the variables. We assume without loss of generality, that $e_1 \leq e_2 \leq e_3$, since any solution $(a,b,c)$ can be re-ordered in such a way, that this will hold. This ordering also implies that $a \leq b \leq c$, since $ab - c \leq ac -b$ $\Leftrightarrow$ $a(b-c) \leq c - b$. If $b\neq c$, either $b-c$ or $c-b$ must be negative and the equation implies that this is $b-c$, hence $b \leq c$. The case $a \leq b$ is analogous.
FACT 1. None of the integers $a,b,c$ can be equal to $1$.
Subproof: Assume wlog that $a=1$, hence $b-c=2^{e_1}$ and $c-b=2^{e_2}$, addition yields $0 = 2^{e_1}+2^{e_2}$, which is impossible.
Q.e.d.
FACT 2. It holds $e_i \neq e_j$, for $i \neq j$ except for the two solutions $(a,b,c) = (2,2,2)$ or $(a,b,c) = (2,2,3)$.
Subproof:
1) $e_1 = e_2 = e_3$: Here we get $ab - c = ac - b = bc - a$. Adding the first two yields $(a+1)(b-c) = $, hence $b=c$. Addition of the later two yields $(c+1)(a-b) = 0$, so $a=b=c$ and $a(a-1) = 2^{e_1}$, which is only possible for $a = 2$, so $(a,b,c) = (2,2,2)$.
2) $e_1 = e_2 < e_3$: Here we only have $ab - c = ac - b$, which is equal to $(a+1)(b-c) = 0$, hence $b = c$, thus $(a-1)b = 2^{e_1}$. The case $e_1=0$ is not possible, since it $b > 1$ (due to FACT 1). So either:
2.1) $a = 2$ and $b = 2^{e_1} = c$: Thus $2^{e_1}2^{e_1} - 2 = 2^{e_2}$ which is $$2^{2e_1 - 1} - 1 = 2^{e_2-1}$$ But the only two powers of two that are close by $1$ are $2^1-2^0 = 1$. Hence $e_1 = e_2 = 1$, which leads again to $(a,b,c) = (2,2,2)$.
2.2) $a$ is odd and $b,c$ even: We have $b^2 - a = 2^{e_3}$. Reducing modulo $2$ yields $0 - 1 \equiv 0\pmod{2}$, which is false and there is no solution.
3) $e_1 < e_2 = e_3$: Here we have $ac - b = bc - a$ which is $(c+1)(a-b) = 0$, so $a = b$. and $a(c-1) = 2^{e_2} = 2^{e_3}$. So either:
3.1) The case $c = 2$ and $a=2^{e_2}$, leads again to $(a,b,c) = (2,2,2)$.
3.2) $c$ is odd and $a,b$ even: Then it is $a(c-1) = 2^{e_2}$ and $a^2 - c = 2^{e_1}$. Reducing the later mod $2$: $0 - 1 \equiv 2^{e_1}\pmod{2}$, so $e_1 = 0$. Hence $a^2 = 1 + c$. Thus $a(c-1) = a(a^2-2) = 2^{e_2}$. Since $a | 2^{e_2}$ it is $a = 2 = b$ and from $a^2 - 1 = c = 3$. Hence we get the solution $(a,b,c) = (2,2,3)$ and its permutations.
4) The case $e_1 = e_3$ is equal to $e_1=e_2=e_3$ since $e_1 \leq e_2 \leq e_3$.
Q.e.d.
For the rest we can safely assume that $e_1 < e_2 < e_3$ since all other cases are covered by FACT 2. If $0 < e_1$ it is easy to see that either $a,b,c$ are all odd or all even:
\begin{array}{| c | c | c | c | c | c | c |}
\hline
\text{mod } 2 & a & b & c & \text{I} & \text{II} & \text{III} \\
\hline
& 0 & 0 & 0 & 0 & 0 & 0 \\
& 0 & 0 & 1 & 1 & 0 & 0 \\
& 0 & 1 & 0 & 0 & 1 & 0 \\
& 0 & 1 & 1 & 1 & 1 & 1 \\
& 1 & 0 & 0 & 1 & 0 & 0 \\
& 1 & 0 & 1 & 1 & 1 & 1 \\
& 1 & 1 & 0 & 1 & 1 & 1 \\
& 1 & 1 & 1 & 0 & 0 & 0 \\
\hline
\end{array}
The table shows, that only the first or the last combination are valid combinations for $a,b,c$ modulo $2$, since only in these combinations I, II and III are valid modulo $2$.
A) If $e_1 > 0$ then $a\equiv b \equiv c \mod{2}$.
A.1) $a\equiv b \equiv c \equiv 0\pmod{2}$. So $a,b$ and $c$ are even. We start by subtracting II from the III:
\begin{align*}
bc-a - (ac-b) & = 2^{e_3}-2^{e_2} \\
c(b-a) - a + b & = 2^{e_2}(2^{e_3-e_2}-1) \\
(c+1)(b-a) & = 2^{e_2}(2^{e_3-e_2}-1) \\
\end{align*} Since $c+1$ is odd, it is $2^{e_2} | (b-a)$ and we can write $a = x + 2^{e_2}l_1$ as well as $b = x + 2^{e_2}l_2$ with integers $l_1, l_2 \geq 0$. Reducing II modulo $2^{e_2}$ yields
\begin{align*}
ac - b & = 2^{e_2}\\
xc-x & \equiv 0 \pmod{2^{e_2}}\\
x(c-1) & \equiv 0 \pmod{2^{e_2}}
\end{align*} since $(c-1)$ is odd, it is $x \equiv 0\pmod{2^{e_2}}$, so $2^{e_2} | a$ and $2^{e_2}| b$. We write $a = 2^{e_2}a'$ and $b = 2^{e_2}b'$ and use this in I: $$2^{e_2}a'2^{e_2}b' - c = 2^{e_1}$$ since $0 < e_1 < e_2$ this yields $2^{e_1} | c$. Applying this to III, with $2^{e_1}c' = c$, it is: $$2^{e_2}b'2^{e_1}c' - 2^{e_2}a' = 2^{e_3}$$ and $$b'2^{e_1}c' - a' = 2^{e_3-e_2} \geq 2^1 $$, so we found another factor of $2$ in $a'$, i.e., $2 | a'$. So we know that $2^{e_2+1} | a \Rightarrow a > 2^{e_2}$, but this leads to:
\begin{align*}
ac - b & = 2^{e_2} \\
2^{e_2}c - b & < 2^{e_2} \\
2^{e_2}b - b & < 2^{e_2} \\
(2^{e_2}- 1)b & < 2^{e_2} \\
\end{align*} Since $0 < e_1 < e_2$, $e_2$ is at least $2$, so the last inequality is only possible for $b = 1$ which contradicts FACT1.
So the "all even" case, does not lead to a solution!
A.2) $a\equiv b \equiv c \equiv 1\pmod{2}$. We start in the same way as in case A.1 and use the equation
\begin{equation}
(\text{Eq.1}) (c+1)(b-a) = 2^{e_2}(2^{e_3-e_2}-1)
\end{equation} But here, we also add II and III which yields:
\begin{equation}
(\text{Eq.2}) (c-1)(b+a) = 2^{e_2}(2^{e_3-e_2}+1)
\end{equation} Since $c$ is odd and larger than $1$, either $c+1$ is dividable by $4$ and $(c-1)/2$ is odd or the other way round.
A.2.1) Assume $c-1 \equiv 0\pmod{4}$, hence $(c+1)/2$ is odd. So $b \equiv a\pmod{2^{e_2-1}}$. We write $a = x + 2^{e_2-1}l_1$ and $b = x + 2^{e_2-1}l_2$, with $x$ odd. Then
\begin{align*}
ac - b & = 2^{e_2}\\
xc-x & \equiv 0 \pmod{2^{e_2-1}}\\
x(c-1) & \equiv 0 \pmod{2^{e_2-1}}
\end{align*} hence $c-1 \equiv 0 \pmod{2^{e_2-1}}$, so $c > 1 + 2^{e_2-1} > 2^{e_2-1}$. Equivalently, $2c > 2^{e_2}$, hence $$ac - b = 2^{e_2} < 2c$$ which is $$(a-2)c < b$$, since $c\geq b$ this implies $a=2$ which contradicts that $a$ is odd.
A.2.2) Assume $c+1 \equiv 0\pmod{4}$, hence $(c-1)/2$ is odd. So $a \equiv -b\pmod{2^{e_2-1}}$. Hence $a = x + 2^{e_2-1}l_1$ and $b = -x + 2^{e_2-1}l_2$ so we get write $ac - b = 2^{e_2}$ as $$x(c+1) \equiv 0 \pmod{2^{e_2-1}}$$ with $x$ odd, hence $c+1 \geq 2^{e_2-1}$, that if $2c + 2 \geq 2^{e_2}$, so we have $$ac-b \leq 2c+2 \Leftrightarrow (a-2)c \leq b+2$$ Since $b \leq c$ it could be $c = b$ but then $a=4$, which contradicts that $a$ is odd, likewise $a=2$. So it must be $c > b$ and we get $a=3$ and $c = b + 2$. Using this in I and II:
\begin{align*}
ab - c = 3b - (b+2) & = 2b - 2 = 2^{e_1} \\
ac - b = 3(b+2) - b & = 2b + 6 = 2^{e_2} \\
\end{align*} hence $$2^{e_2} - 2^{e_1} = 8$$. But the only perfect powers of two which are $8$ apart are $2^4 - 2^3 = 2^3$, hence $2b - 2 = 8$ so $b=5$ and $b+2 = c = 7$: $(a,b,c) = (3,5,7)$
So the "all odd" case, leads to a solution. Next, we assume, that the smallest exponent $e_1$ is zero.
B) If $e_1 = 0$, and $0 < e_2 < e_3$ it is $a \equiv b \equiv 0\pmod{2}$ and $c \equiv 1 \pmod{2}$. We start again from the equations
\begin{equation}
(\text{Eq.1}) (c+1)(b-a) = 2^{e_2}(2^{e_3-e_2}-1)
\end{equation}
\begin{equation}
(\text{Eq.2}) (c-1)(b+a) = 2^{e_2}(2^{e_3-e_2}+1)
\end{equation} We apply the same reasoning:
B.2.1) Assume $c-1 \equiv 0\pmod{4}$, hence $(c+1)/2$ is odd. But from
$$ab - c = 2^{e_1} = 1$$ follows $ab = c+1$ and thus $$\frac{a}{2}b = \frac{c+1}{2}$$, but $b$ is also even, this is impossible.
B.2.2) Assume $c+1 \equiv 0\pmod{4}$, hence $(c-1)/2$ is odd. So $a \equiv -b\pmod{2^{e_2-1}}$. Hence $a = x + 2^{e_2-1}l_1$ and $b = -x + 2^{e_2-1}l_2$ and $x$ even. If $l_1 > 0$ it is $a \geq 2^{e_2-1}$ hence
$2^{e_2-1}c - b < ac - b = 2^{e_2}$ thus $$2^{e_2-1}(c-2) < b$$. Note that $e_1 = 0 \leq e_2 - 1$, hence $b < c < b+2$, hence $b+1 = c$. So $ac-a-c=1$, hence $(a-1)c = a+1$ which is equivalent to $$c = 1 + \frac{2}{a-1}$$, the only even $a$ that makes $c$ an integer is $a=2$, hence $c=3$ and thus $b=2$. The solution is equal to FACT 2 $(a,b,c) = (2,2,3)$.
So we have $l_1=0$, so $a = x$ hence $a+b = 2^{e_2-1}l_2$. If $l_2 > 1$, it is $a+b \geq 2^{e_2}$ hence $ac - b = 2^{e_2} \leq a + b$ thus $$a(c-1) \leq 2b$$ since $a$ is even $$c-1 \leq \frac{a}{2}(c-1) < b$$ which is not possible, since $c$ is odd and $b$ is even and $b \leq c$. So $l_2=1$. Hence $a+b=2^{e_2-1}$. We multiply this by $2$ which makes it equal to II:
\begin{align*}
2(a+b) & = 2\cdot 2^{e_2-1} \\
2a + 2b & = 2^{e_2} = ac - b \\
3b & = a(c-2) \\
\frac{3b}{a} - c & = -2 \\
\end{align*} This we subtract from $ab - c = 1$: $$ab - c - \frac{3b}{a} + c = 3$$ hence
\begin{align*}
b\left(a - \frac{3}{a}\right) & = 3 \\
b\left(\frac{a^2 - 3}{a}\right) & = 3 \\
\end{align*} But $a \nmid a^2 - 3$ except if $a=3$ which is not possible since $a$ is even. Hence $a | b$ and $$\frac{b}{a}(a^2-3) = 3$$ Already for $a=4$ this is impossible since $4^2 - 3 = 13 > 3$. Hence $a=2$. From this we get $\frac{b}{2}(2^2-3) = 3$ which yields $b=6$ and from $ab - c = 12-c = 11$ we get $c=11$. So the last solution is: $(a,b,c) = (2,6,11)$.
So in total there are the solutions $$(a,b,c) = \{(2,2,2),(2,2,3),(3,5,7),(2,6,11)\}$$ and their permutations.
Q.e.d.
| Puzzle 1: Find all triples of integers $(a,b,c) \in \mathbb{N}^3_{> 0}$ such that $$\text{I)}\;ab-c = 2^{e_1}, \;\; \text{II)}\;ac-b = 2^{e_2}, \;\; \text{III)}\; bc-a = 2^{e_3}$$ with $(e_1,e_2,e_3) \in \mathbb{N}^3$ |
If you have some free hours, try it for yourself. I don't think that the proof below the fold is very nice or beautiful, and also for my taste distinguished too many cases, but it is overall not that hard to follow.
Before we distinguish two cases, let me first proof two facts which concerns special cases of the variables. We assume without loss of generality, that $e_1 \leq e_2 \leq e_3$, since any solution $(a,b,c)$ can be re-ordered in such a way, that this will hold. This ordering also implies that $a \leq b \leq c$, since $ab - c \leq ac -b$ $\Leftrightarrow$ $a(b-c) \leq c - b$. If $b\neq c$, either $b-c$ or $c-b$ must be negative and the equation implies that this is $b-c$, hence $b \leq c$. The case $a \leq b$ is analogous.
FACT 1. None of the integers $a,b,c$ can be equal to $1$.
Subproof: Assume wlog that $a=1$, hence $b-c=2^{e_1}$ and $c-b=2^{e_2}$, addition yields $0 = 2^{e_1}+2^{e_2}$, which is impossible.
Q.e.d.
FACT 2. It holds $e_i \neq e_j$, for $i \neq j$ except for the two solutions $(a,b,c) = (2,2,2)$ or $(a,b,c) = (2,2,3)$.
Subproof:
1) $e_1 = e_2 = e_3$: Here we get $ab - c = ac - b = bc - a$. Adding the first two yields $(a+1)(b-c) = $, hence $b=c$. Addition of the later two yields $(c+1)(a-b) = 0$, so $a=b=c$ and $a(a-1) = 2^{e_1}$, which is only possible for $a = 2$, so $(a,b,c) = (2,2,2)$.
2) $e_1 = e_2 < e_3$: Here we only have $ab - c = ac - b$, which is equal to $(a+1)(b-c) = 0$, hence $b = c$, thus $(a-1)b = 2^{e_1}$. The case $e_1=0$ is not possible, since it $b > 1$ (due to FACT 1). So either:
2.1) $a = 2$ and $b = 2^{e_1} = c$: Thus $2^{e_1}2^{e_1} - 2 = 2^{e_2}$ which is $$2^{2e_1 - 1} - 1 = 2^{e_2-1}$$ But the only two powers of two that are close by $1$ are $2^1-2^0 = 1$. Hence $e_1 = e_2 = 1$, which leads again to $(a,b,c) = (2,2,2)$.
2.2) $a$ is odd and $b,c$ even: We have $b^2 - a = 2^{e_3}$. Reducing modulo $2$ yields $0 - 1 \equiv 0\pmod{2}$, which is false and there is no solution.
3) $e_1 < e_2 = e_3$: Here we have $ac - b = bc - a$ which is $(c+1)(a-b) = 0$, so $a = b$. and $a(c-1) = 2^{e_2} = 2^{e_3}$. So either:
3.1) The case $c = 2$ and $a=2^{e_2}$, leads again to $(a,b,c) = (2,2,2)$.
3.2) $c$ is odd and $a,b$ even: Then it is $a(c-1) = 2^{e_2}$ and $a^2 - c = 2^{e_1}$. Reducing the later mod $2$: $0 - 1 \equiv 2^{e_1}\pmod{2}$, so $e_1 = 0$. Hence $a^2 = 1 + c$. Thus $a(c-1) = a(a^2-2) = 2^{e_2}$. Since $a | 2^{e_2}$ it is $a = 2 = b$ and from $a^2 - 1 = c = 3$. Hence we get the solution $(a,b,c) = (2,2,3)$ and its permutations.
4) The case $e_1 = e_3$ is equal to $e_1=e_2=e_3$ since $e_1 \leq e_2 \leq e_3$.
Q.e.d.
For the rest we can safely assume that $e_1 < e_2 < e_3$ since all other cases are covered by FACT 2. If $0 < e_1$ it is easy to see that either $a,b,c$ are all odd or all even:
\begin{array}{| c | c | c | c | c | c | c |}
\hline
\text{mod } 2 & a & b & c & \text{I} & \text{II} & \text{III} \\
\hline
& 0 & 0 & 0 & 0 & 0 & 0 \\
& 0 & 0 & 1 & 1 & 0 & 0 \\
& 0 & 1 & 0 & 0 & 1 & 0 \\
& 0 & 1 & 1 & 1 & 1 & 1 \\
& 1 & 0 & 0 & 1 & 0 & 0 \\
& 1 & 0 & 1 & 1 & 1 & 1 \\
& 1 & 1 & 0 & 1 & 1 & 1 \\
& 1 & 1 & 1 & 0 & 0 & 0 \\
\hline
\end{array}
The table shows, that only the first or the last combination are valid combinations for $a,b,c$ modulo $2$, since only in these combinations I, II and III are valid modulo $2$.
A) If $e_1 > 0$ then $a\equiv b \equiv c \mod{2}$.
A.1) $a\equiv b \equiv c \equiv 0\pmod{2}$. So $a,b$ and $c$ are even. We start by subtracting II from the III:
\begin{align*}
bc-a - (ac-b) & = 2^{e_3}-2^{e_2} \\
c(b-a) - a + b & = 2^{e_2}(2^{e_3-e_2}-1) \\
(c+1)(b-a) & = 2^{e_2}(2^{e_3-e_2}-1) \\
\end{align*} Since $c+1$ is odd, it is $2^{e_2} | (b-a)$ and we can write $a = x + 2^{e_2}l_1$ as well as $b = x + 2^{e_2}l_2$ with integers $l_1, l_2 \geq 0$. Reducing II modulo $2^{e_2}$ yields
\begin{align*}
ac - b & = 2^{e_2}\\
xc-x & \equiv 0 \pmod{2^{e_2}}\\
x(c-1) & \equiv 0 \pmod{2^{e_2}}
\end{align*} since $(c-1)$ is odd, it is $x \equiv 0\pmod{2^{e_2}}$, so $2^{e_2} | a$ and $2^{e_2}| b$. We write $a = 2^{e_2}a'$ and $b = 2^{e_2}b'$ and use this in I: $$2^{e_2}a'2^{e_2}b' - c = 2^{e_1}$$ since $0 < e_1 < e_2$ this yields $2^{e_1} | c$. Applying this to III, with $2^{e_1}c' = c$, it is: $$2^{e_2}b'2^{e_1}c' - 2^{e_2}a' = 2^{e_3}$$ and $$b'2^{e_1}c' - a' = 2^{e_3-e_2} \geq 2^1 $$, so we found another factor of $2$ in $a'$, i.e., $2 | a'$. So we know that $2^{e_2+1} | a \Rightarrow a > 2^{e_2}$, but this leads to:
\begin{align*}
ac - b & = 2^{e_2} \\
2^{e_2}c - b & < 2^{e_2} \\
2^{e_2}b - b & < 2^{e_2} \\
(2^{e_2}- 1)b & < 2^{e_2} \\
\end{align*} Since $0 < e_1 < e_2$, $e_2$ is at least $2$, so the last inequality is only possible for $b = 1$ which contradicts FACT1.
So the "all even" case, does not lead to a solution!
A.2) $a\equiv b \equiv c \equiv 1\pmod{2}$. We start in the same way as in case A.1 and use the equation
\begin{equation}
(\text{Eq.1}) (c+1)(b-a) = 2^{e_2}(2^{e_3-e_2}-1)
\end{equation} But here, we also add II and III which yields:
\begin{equation}
(\text{Eq.2}) (c-1)(b+a) = 2^{e_2}(2^{e_3-e_2}+1)
\end{equation} Since $c$ is odd and larger than $1$, either $c+1$ is dividable by $4$ and $(c-1)/2$ is odd or the other way round.
A.2.1) Assume $c-1 \equiv 0\pmod{4}$, hence $(c+1)/2$ is odd. So $b \equiv a\pmod{2^{e_2-1}}$. We write $a = x + 2^{e_2-1}l_1$ and $b = x + 2^{e_2-1}l_2$, with $x$ odd. Then
\begin{align*}
ac - b & = 2^{e_2}\\
xc-x & \equiv 0 \pmod{2^{e_2-1}}\\
x(c-1) & \equiv 0 \pmod{2^{e_2-1}}
\end{align*} hence $c-1 \equiv 0 \pmod{2^{e_2-1}}$, so $c > 1 + 2^{e_2-1} > 2^{e_2-1}$. Equivalently, $2c > 2^{e_2}$, hence $$ac - b = 2^{e_2} < 2c$$ which is $$(a-2)c < b$$, since $c\geq b$ this implies $a=2$ which contradicts that $a$ is odd.
A.2.2) Assume $c+1 \equiv 0\pmod{4}$, hence $(c-1)/2$ is odd. So $a \equiv -b\pmod{2^{e_2-1}}$. Hence $a = x + 2^{e_2-1}l_1$ and $b = -x + 2^{e_2-1}l_2$ so we get write $ac - b = 2^{e_2}$ as $$x(c+1) \equiv 0 \pmod{2^{e_2-1}}$$ with $x$ odd, hence $c+1 \geq 2^{e_2-1}$, that if $2c + 2 \geq 2^{e_2}$, so we have $$ac-b \leq 2c+2 \Leftrightarrow (a-2)c \leq b+2$$ Since $b \leq c$ it could be $c = b$ but then $a=4$, which contradicts that $a$ is odd, likewise $a=2$. So it must be $c > b$ and we get $a=3$ and $c = b + 2$. Using this in I and II:
\begin{align*}
ab - c = 3b - (b+2) & = 2b - 2 = 2^{e_1} \\
ac - b = 3(b+2) - b & = 2b + 6 = 2^{e_2} \\
\end{align*} hence $$2^{e_2} - 2^{e_1} = 8$$. But the only perfect powers of two which are $8$ apart are $2^4 - 2^3 = 2^3$, hence $2b - 2 = 8$ so $b=5$ and $b+2 = c = 7$: $(a,b,c) = (3,5,7)$
So the "all odd" case, leads to a solution. Next, we assume, that the smallest exponent $e_1$ is zero.
B) If $e_1 = 0$, and $0 < e_2 < e_3$ it is $a \equiv b \equiv 0\pmod{2}$ and $c \equiv 1 \pmod{2}$. We start again from the equations
\begin{equation}
(\text{Eq.1}) (c+1)(b-a) = 2^{e_2}(2^{e_3-e_2}-1)
\end{equation}
\begin{equation}
(\text{Eq.2}) (c-1)(b+a) = 2^{e_2}(2^{e_3-e_2}+1)
\end{equation} We apply the same reasoning:
B.2.1) Assume $c-1 \equiv 0\pmod{4}$, hence $(c+1)/2$ is odd. But from
$$ab - c = 2^{e_1} = 1$$ follows $ab = c+1$ and thus $$\frac{a}{2}b = \frac{c+1}{2}$$, but $b$ is also even, this is impossible.
B.2.2) Assume $c+1 \equiv 0\pmod{4}$, hence $(c-1)/2$ is odd. So $a \equiv -b\pmod{2^{e_2-1}}$. Hence $a = x + 2^{e_2-1}l_1$ and $b = -x + 2^{e_2-1}l_2$ and $x$ even. If $l_1 > 0$ it is $a \geq 2^{e_2-1}$ hence
$2^{e_2-1}c - b < ac - b = 2^{e_2}$ thus $$2^{e_2-1}(c-2) < b$$. Note that $e_1 = 0 \leq e_2 - 1$, hence $b < c < b+2$, hence $b+1 = c$. So $ac-a-c=1$, hence $(a-1)c = a+1$ which is equivalent to $$c = 1 + \frac{2}{a-1}$$, the only even $a$ that makes $c$ an integer is $a=2$, hence $c=3$ and thus $b=2$. The solution is equal to FACT 2 $(a,b,c) = (2,2,3)$.
So we have $l_1=0$, so $a = x$ hence $a+b = 2^{e_2-1}l_2$. If $l_2 > 1$, it is $a+b \geq 2^{e_2}$ hence $ac - b = 2^{e_2} \leq a + b$ thus $$a(c-1) \leq 2b$$ since $a$ is even $$c-1 \leq \frac{a}{2}(c-1) < b$$ which is not possible, since $c$ is odd and $b$ is even and $b \leq c$. So $l_2=1$. Hence $a+b=2^{e_2-1}$. We multiply this by $2$ which makes it equal to II:
\begin{align*}
2(a+b) & = 2\cdot 2^{e_2-1} \\
2a + 2b & = 2^{e_2} = ac - b \\
3b & = a(c-2) \\
\frac{3b}{a} - c & = -2 \\
\end{align*} This we subtract from $ab - c = 1$: $$ab - c - \frac{3b}{a} + c = 3$$ hence
\begin{align*}
b\left(a - \frac{3}{a}\right) & = 3 \\
b\left(\frac{a^2 - 3}{a}\right) & = 3 \\
\end{align*} But $a \nmid a^2 - 3$ except if $a=3$ which is not possible since $a$ is even. Hence $a | b$ and $$\frac{b}{a}(a^2-3) = 3$$ Already for $a=4$ this is impossible since $4^2 - 3 = 13 > 3$. Hence $a=2$. From this we get $\frac{b}{2}(2^2-3) = 3$ which yields $b=6$ and from $ab - c = 12-c = 11$ we get $c=11$. So the last solution is: $(a,b,c) = (2,6,11)$.
So in total there are the solutions $$(a,b,c) = \{(2,2,2),(2,2,3),(3,5,7),(2,6,11)\}$$ and their permutations.
Q.e.d.
Comments
Post a Comment