# Computing greatest common divisor and determining whether Diophantine equation has solutions

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.

$(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.

• I am not familiar with mod operation. I was taught the Euclidean algorithm by repeatedly using the division algorithm. – user444945 Aug 17 '17 at 21:28
• @Josh I used $\ (a,b) = (a,b')\,$ if $\,a\mid b-b',\,$ i.e. if $\, b\equiv b'\pmod a,\,$ i.e. Euclid's algorithm. – Bill Dubuque Aug 17 '17 at 21:30
• Could you show me how to do it by repeatedly using the division algorithm? – user444945 Aug 17 '17 at 21:31
• @Josh $\ a\mid b-b'\Rightarrow\, b = qa + b'\,$ so $\, (a,b) = (a,\,qa+b') = (a,b')\,$ in division language. The common form of Euclid's algorithm chooses $\,b' = b\bmod a =\,$ remainder of $\, b\div a,\,$ i.e. the least possible such $b'$ that is $\ge 0$ (but that is not always the most convenient choice). – Bill Dubuque Aug 17 '17 at 21:38
• Oh I see. I understand now. Is my argument for part b and part c correct? – user444945 Aug 17 '17 at 21:56

$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$$

• It'd help to say how you factored $\,3+2^{\large 8}\,$ (no nontrivial factorization is needed if we use Euclid's algorithm). – Bill Dubuque Aug 17 '17 at 21:26
• I did not factor it, i just calculated it and then divide it with 7 – Aqua Aug 17 '17 at 21:29
• I am not allowed to use calculators. – user444945 Aug 17 '17 at 21:30
• Well i did it without calculator. – Aqua Aug 17 '17 at 21:32
• I just edit it. – Aqua Aug 17 '17 at 21:42