2
$\begingroup$

Problem: What is that largest positive integer $n$ for which $n^3+100$ is divisible by $n+10$?

The solution from Art of Problem Solving: If $n+10 \mid n^3+100$, $\gcd(n^3+100,n+10)=n+10$. Using the Euclidean algorithm, we have $\gcd(n^3+100,n+10)= \gcd(-10n^2+100,n+10)$ $= \gcd(100n+100,n+10)$ $= \gcd(-900,n+10)$, so $n+10$ must divide $900$. The greatest integer $n$ for which $n+10$ divides $900$ is $\boxed{890}$; we can double-check manually and we find that indeed $900\mid 890^3+100$.


Question: How can $\gcd(n^3+100,n+10)= \gcd(-10n^2+100,n+10)$ $= \gcd(100n+100,n+10)$?

$\endgroup$
1
  • $\begingroup$ Are you aware $\gcd(A,B) = \gcd(A \pm kB, B)$ for any integer $k$? $n^3+100 = n^3 + 10n^2 - 10n^2 + 100= n^2(n+10) -10n^2 + 100$ so $\gcd(n^3 + 100, n+10) = \gcd(n^2(n+10)-10n^2 + 100, n+10) = \gcd(-10n^2 + 100, n+100)$. $\endgroup$
    – fleablood
    Sep 19 at 4:39
3
$\begingroup$

You know that $n$ 'acts as' $-10$, since

$$n \equiv -10 \quad \text { mod } (n + 10)$$ like so:

$$n^3 + 100 = (n + 10 - 10)n^2 + 100 = \underbrace{(n+10)n^2}_\text{multiple of (n+10)} - 10n^2 + 100$$ You could 'cheat' and plug in $-10$ immediately:

$$\gcd(n^3 + 100, n+ 10) = \gcd(-900, n+ 10)$$

$\endgroup$
2
  • $\begingroup$ gcd(100n+100,n+10) here 100n+100 how I derived? $\endgroup$ Sep 19 at 1:04
  • $\begingroup$ @ABIDB11152 like so: $$ -10n^2 + 100 = -10(n+10-10)n + 100 = -10n(n+10) + 100n + 100$$ $\endgroup$
    – JuliusL33t
    Sep 19 at 9:27
1
$\begingroup$

The Euklidean Algorithm uses the fact that $$\gcd(a,b)=\gcd(a+kb,b)$$ We choose $k=-n^2$ so that the $n^3$ term will be removed. We get $$\gcd(n^3+100,n+10)= \gcd((n^3+100)-n^2(n+10),n+10)$$ So we have $$=\gcd(-10n^2+100,n+10)$$ Now we remove $n^2$ by choosing $k=10n$ $$=\gcd((-10n^2+100)+10n(n+10),n+10)$$ $$=\gcd(100n+100,n+10)$$ and now for $k=-100$ we get $$=\gcd((100n+100)-100(n+10),n+10)$$ $$=\gcd(-900,n+10)$$

$\endgroup$
1
$\begingroup$

You can perform long division to obtain the following result, $$n^3+100=(n^2-10n+100)(n+10)-900$$ $$\implies n+10\mid 900$$ Therefore the largest value of $n=890$.

$\endgroup$
0
$\begingroup$

$\gcd(A,B) = \gcd(A \pm kB, B)$ for any integer $k$.

For example $\gcd(58, 16) = \gcd(3\times 16 + 10, 16) = \gcd(3\times 16+ 10-3\times 16, 16) = \gcd(10, 16)$.

......

So $\gcd(n^3 + 100, n+10) = \gcd(n^2(n+10) - 10n^2 + 100, n+10)=$

$ \gcd(n^2(n+10) - 10n^2 + 100- n^2(n+10), n+10)=\gcd(-10n^2 + 100, n+10)=$

$\gcd(-10n(n + 10) +100n + 100, n+10) = \gcd(-10n(n+10) + 10n + 100 + 10n(n+10), n+10)=$

$\gcd(10n + 100, n+10)$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.