Saturday, 14 March 2026

Exercise (5.2).8

Solve the linear congruences

$$ 15x_j ≡ b_j \pmod {32} $$

for $b_j = 5, 7, 9, 11, 13$.


Since $\gcd(15,32)=1$, we can use Euler's Theorem,

$$ 15^{\phi(32)} \equiv 1 \pmod {32} $$

Using $\phi(32)=16$ gives us

$$ \begin{align} 15^{16} & \equiv 1 \pmod {32} \\ \\ 15 \times (15^{15} \times b_j) & \equiv b_j \pmod {32} \end{align}$$

Noting that $15^2 \equiv 225 \equiv 1 \pmod{32}$, gives us $15^{15} \equiv (15^2)^7 \times 15 \equiv 1^7 \times 15 \equiv 15 \pmod {32}$

And so

$$ \begin{align} 15 \times (15^{15} \times b_j) & \equiv b_j \pmod {32} \\ \\ 15 \times (15 \times b_j) & \equiv b_j \pmod {32}  \end{align}$$

The following table shows the values of $15 \times b_j \pmod {32}$

b_j15 b_j mod 32
511
79
97
115
133

The solutions for $x_j$ are $11, 9, 7, 5, 3$ for $b_j = 5, 7, 9, 11, 13$, respectively.