Un Calcul al CMMDC

 Problema Proprie

        Sa se determine $gcd(3\cdot n+1\;,\;5\cdot n+7)$.

SOLUTIE CiP

RASPUNS CiP  $(3\cdot n+1,5\cdot n+7)=\begin{cases}1,\;\;if\;n=2\cdot k \\2,\;if\;\;n=4\cdot k+3\\4,\;\;if\;n=8\cdot k+1\\8,\;\;if\;n=16\cdot k+13\\16,\;if\;n=16\cdot k+5\end{cases}$

REZOLVARE CiP

     Pe baza proprietatilor gcd

$(a,b)=(a+b\cdot m,b)=(a,b+a \cdot m)$ , for any integers $m$;

avem succesiv

 $(3n+1,5n+7)=(3n+1,5n+7-(3n+1))=(3n+1,2n+6)=(3n+1-(2n-6),2n+6)=$

$=(n-5,2n+6)=(n-5,2n+6-2(n-5))=$

$= (n-5,16)=\begin{cases}16,\;if\;n-5=16\cdot k\\8\;if\;n-5=16\cdot k+8\\4,\;if\;n-5 =16\cdot k+4\;or\;n-5=16\cdot k+12\\2\;if\;n-5=16\cdot k+\;2\;or\;6\;or\;10\;or\;14\\1\;if\;n-5=16\cdot k+\;1\;or\;3\;or\;5\;or\;7\;or\;9\;or\;11\;or\;13\;or\;15\end{cases}$

Obtinem imediat raspunsul.

$\blacksquare$