Computing greatest common divisor and determining whether Diophantine equation has solutions

Question

Question:

(1) Compute gcd$(224, 12 + 2^{10})$

(2) Describe in words the set of all integers $ n$ for which the equation $ \ 4x + ny = 1$ has integer solutions.

(3)

Describe in words the set of all integers $ \ n$ for which the equation $ \ 3x + ny = 1$ has integer solutions.

My attempt:

For (1) the Euclidean algorithm will be difficult to use. Should I use the theorem that states gcd$ \ (a,b) = $ gcd($ a -bq, b)$ or should I prime factorize both sides? I am not quite sure.

For (2) we need need gcd$(4,n) = 1$ in order for the equation to have integer solutions. This means that $ \ n$ must belong to the set of all odd integers.

For (3) we need need gcd$(3,n) = 1$ in order for the equation to have integer solutions. This means that $ \ n$ must belong to the set of all integers that are not divisible by 3.

Answer 1

$224= 4\cdot 7\cdot 8$ and $12+2^{10} = 4(3+2^8)=4\cdot 7\cdot 37$.

So $gcd(224,12+2^{10}) =28$.

The rest is fine.

Ok, ok, we can factor $$2^8+3 = 2^8-2^2+4+3= 2^2(2^6-1)+7 = 4(2^3-1)(2^3+1)+7 =4\cdot 7\cdot 9+7 = 7(36+1) =7\cdot 37$$

Answer 2

$(224,12\!+\!2^{10}) = 4(7\cdot 8,\,3\!+\!2^8)= 4\cdot 7\ $ by $\ \begin{align}\\ &\overbrace{(8,3\!+\!\color{#0a0}{2^8}) = (8,3)=1}^{\large\quad\ \ \ \color{#0a0}{2^{\Large 8}}\,\equiv\, 0\pmod{8}}\\ &\underbrace{(7,3\!+\!\color{#c00}{2^8}) = (7,3\!+\!2^2)}_{\large\quad\ \ \ \color{#c00}{2^{\Large 7}}\,\equiv\, 2\pmod 7}=7\end{align}$

---

Or use $\,{\rm mod}\ 224\!:\,\ 2^{\large 8} = 256\equiv 32\,\Rightarrow\, 2^{10}\equiv 4\cdot 32,$ and use Euclid's algorithm.