# Largest positive integer $n$ for which $n^3+100$ is divisible by $n+10$

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

• 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)$. Sep 19 at 4:39

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

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

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

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

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