# divisibility of an expression by 30

let $g$ be a natural number how to show that $30$ divides $(-8 g^5+20 g^4-50 g^3+115 g^2-167 g+90)$?

my guess: $30$ divides $90$ so it is enough to show that $30|-8 g^5+20 g^4-50 g^3+115 g^2-167 g = g(-8 g^4+20 g^3-50 g^2+115 g-167)$ now if $30|g$ we are done, otherwise we have to show that $30|-8 g^4+20 g^3-50 g^2+115 g-167$ , I don't know how to go further..

-

Note that for any $n\in\mathbb{Z}$, $$30\mid n\iff 2\mid n\text{ and }3\mid n\text{ and }5\mid n.$$ Then note that $$-8g^5+20g^4-50g^3+115g^2-167g+90\equiv0+0+0+g^2+g+0\equiv g+g\equiv 0\bmod 2$$ because, by Fermat's Little Theorem, $g^2\equiv g\bmod 2$. Similarly, $$-8g^5+20g^4-50g^3+115g^2-167g+90\equiv g^5+2g^4+g^3+g^2+g+0\equiv$$ $$g+2g^2+g+g^2+g+0\equiv 0\bmod 3$$ because $g^3\equiv g\bmod 3$, and $$-8g^5+20g^4-50g^3+115g^2-167g+90\equiv 2g^5+0+0+0+3g+0\equiv$$ $$2g+0+0+0+3g+0\equiv 0\bmod 5$$ because $g^5\equiv g\bmod 5$.

Thus, we have shown that any number of the form $-8g^5+20g^4-50g^3+115g^2-167g+90$ is divisible by 2, 3, and 5, and therefore is divisible by 30.

-
why do we have: if $2|n$ and $3|n$ and $5|n$ then $30|n$? is it because of the prime factorization $30=2*3*5$, which generalizes to the following: $a=p_1^{k_1}*p_2^{k_2}...p_s^{k_s}$ such that each $p_i$ divides $n$ then $a$ divides $n$, is this true? – palio Oct 12 '11 at 11:15
@palio: In general, if $a\mid n$ and $b\mid n$, then $\text{lcm}(a,b)\mid n$; see here. One may also appeal to the Chinese Remainder Theorem. – Zev Chonoles Oct 12 '11 at 11:23
Thank you zev !!! – palio Oct 12 '11 at 11:38
No problem, glad to help! – Zev Chonoles Oct 12 '11 at 11:40

The polynomial is divisible by 30 iff it is divisible by 2, 3, and 5.

The straightforward approach is then to simply evaluate the polynomial at {0,1} modulo 2, {0,1,2} modulo 3, and {0,1,2,3,4} modulo 5, and verify you get 0 in each case.

-

Hint: Show that each of $2,3,5$ divides your expression. Lets do $2$ first:

We can take out all the terms which are already divisible by $2$, and look at the remainder. (That is look modulo 2) We have $$115g^2-167g\equiv g^2-g.$$ Then if g is odd, this is divisible by two, and same thing if $g$ is even. Now do the same for $3$ and $5$.

-

HINT $\rm\ \mod\ 2\!:\ f\: \equiv\: g^2-g,\ \ mod\ 5\!:\ f\:\equiv\: 2\ (g^5-g),\:$ and $\rm\ mod\ 3\!:\ f(\pm1)\equiv\: 0\:\equiv\:f(0)\:.$

-