¿Cómo encontrar este GCD?

Question

Cómo encontrar GCD de$2n + 3$ y$5n^2 + 3n -1$ (dependiendo de$n$)

¡Gracias por adelantado!

Answer 1

La respuesta es $1$, debido a $(5n^2+3n-1)/(2n+3)=5/2 n-9/4$ resto $23/4$. El siguiente paso del algoritmo de Euclides sería $(2n+3)/(23/4)=\ldots$ sin ningún resto. Por lo tanto,$gcd(5n^2+3n-1,2n+3)=23/4$. Este es un polinomio y puede ser normativa para multiplicar $4/23$ y consigue $gcd(5n^2+3n-1,2n+3)=1$.

Tenga en cuenta que el algoritmo de Euclides no produce un resultado único, porque hay infinitamente muchos multiplicando con constantes como lo hice yo!

El enfoque general para $gcd(p,q)$ es la siguiente:

$$\begin{align}p&=q_1\cdot q+r_1\\q&=q_2\cdot r_1+r_2\\r_1&=q_3\cdot r_2+r_3\\r_2&=q_4\cdot r_3+r_4\\&\;\vdots\end{align}$$

y así sucesivamente. Si usted encuentra un $r_k=0$$gcd(p,q)=r_{k-1}$.

Answer 2

Deje que$d$ sea el gcd. Luego$d| (2n+3)^2=4n^2+12n+9$ y la combinación lineal$4(5n^2+3n-1)-5(4n^2+12n+9)=-48n-49$. También divide$24(2n+3)-48n-49=23$. Por lo tanto, el gcd es$1$ o$23$.

Answer 3

Tenga en cuenta que$2n+3$ siempre es impar. Por lo tanto, el gcd de$2n+3$ y$5n^2+3n-1$ es el mismo que el gcd de$20n^2+12n-4$. Ahora usa el algoritmo euclidiano. Tenga en cuenta que$$20n^2+12n-4=(10n-9)(2n+3)+23.$ $ Así$\gcd(5n^2+3n-1,2n+3)=\gcd(2n+3,23)$. Podríamos pasar por otro paso del algoritmo euclidiano. Pero es más fácil notar que ya que$23$ es primo,$\gcd(2n+3,23)=1$ o$\gcd(2n+3,23)=23$.

El segundo sucede precisamente cuando$2n+3\equiv 0\pmod{23}$, o equivalente cuando$n\equiv 10\pmod{23}$.