1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I am not familiar with mod operation. I was taught the Euclidean algorithm by repeatedly using the division algorithm. $\endgroup$ – user444945 Aug 17 '17 at 21:28
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Aug 17 '17 at 21:30
  • $\begingroup$ Could you show me how to do it by repeatedly using the division algorithm? $\endgroup$ – user444945 Aug 17 '17 at 21:31
  • $\begingroup$ @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). $\endgroup$ – Bill Dubuque Aug 17 '17 at 21:38
  • $\begingroup$ Oh I see. I understand now. Is my argument for part b and part c correct? $\endgroup$ – user444945 Aug 17 '17 at 21:56
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy