Divisibility Challenge: Find Smallest Integer for $f(x)$

[lfdahl]

Let $f(x) = 5x^{13}+13x^5+9\cdot a \cdot x$

Find the smallest possible integer, $a$, such that $65$ divides $f(x)$ for every integer $x$.

 

[Deveno]

Finally, some abstract algebra pays off!

[sp]First of all, note that $65|(5x^{13}+13x^5 + 9ax) \iff 5|(5x^{13}+13x^5 + 9ax)$ and $13|(5x^{13}+13x^5 + 9ax)$.

This suggests looking at the given polynomial mod 5 and mod 13.

Mod 5 we have:

$3x^5 + 4ax = 0$ (since we want 5 to divide the expression on the left).

$x(3x^4 + 4a) = 0$

Since $x$ can be some integer co-prime to 5, we will assume $x \neq 0$ (mod 5). Thus:

$3x^4 + 4a = 3 + 4a = 0$, that is:

$4a = 2$ (mod 5) so that:

$a = 3$ (mod 5).

Mod 13 we have:

$5x^{13} + 9ax = 0$ (since we want the expression on the left to be divisible by 13), thus:

$x(5x^{12} + 9a) = 0$. Again, we may assume $x \neq 0$ (mod 13), so we have:

$5x ^{12} + 9a = 5 + 9a = 0$ thus:

$9a = 8$ (mod 13), so that:

$a = 11$ (mod 13).

Since 5 and 13 are prime, we can apply the Chinese Remainder theorem to obtain:

$a = (3)(13)[13^{-1}]_5 + 11(5)[5^{-1}]_{13} = (3)(13)(2) + (11)(5)(8) = 78 + 440 = 518 = 65*7 + 63 = 63$ (mod 65).

Depending on if you meant:

the smallest POSITIVE value for $a$, we obtain: $a = 63$

the smallest absolute value for $a$, we obtain $a = -2$

there is no "smallest" such $a$ given the usual ordering of the real numbers, since the set of solutions contains infinitely many negative integers.[/sp]

 

[kaliprasad]

Spoiler

$f(x) = x(5x^{12} + 13x^4 + 9a)$
x can be factored out so 65 should divide $5x^{12} + 13x^4 + 9a$

65 = 13 * 5

So taking mod 5 we have $13x^4\, + 9a\, mod\, 5 = 0$
It is true for any x so take x co-prime to 5 so we have x^4 = 1

So we get 13 + 9a mod 5 = 0 or 3 – a mod 5 = 0 or a = 3 mod 5

Similarly we have $5x^{12} + 9a \,mod \,13 = 0$ or 5 + 9a mod 13 = 0 or a = 11 mod 13

a = 3 mod 5 and a = 11 mod 13 can be solved by using chinees remainder theorem also but we see that
a = -2 mod 5 and a = -2 mod 13 so a = -2 mod 65 or 63
a = 63 + 65n and a = 63 is the lowest positive integer

 

[lfdahl]

Thankyou and well done Deveno and kaliprasad for your thorough and correct answers.
You´re absolutely right, Deveno, I should have pointed out, that it is the smallest positive integer a, I was looking for.

Solution by other:

Spoiler

\[f(x)\equiv 0 \: \: \: (mod\: \: \: 65)\\\\ 5\cdot x^{13}+13\cdot x^5+9\cdot a\cdot x \equiv 0 \: \: \: (mod\: \: \: 65)\\\\\]

Applying "Fermats little theorem":

\[5\cdot x^{13}\equiv 5x \: \:\: (mod\: \: \: 65)\\\\ 13\cdot x^{5}\equiv 13x \: \:\: (mod\: \: \: 65)\\\\\]
\[5x + 13x + 9ax \equiv 0 \: \:\: (mod\: \: \: 65)\\\\ 9x(2+a)\equiv 0\: \:\: (mod\: \: \: 65)\\\\\]
Thus
$$2+a\equiv 0\: \:\: (mod\: \: \: 65) \Rightarrow a = 63$$

 

[CellCoree]

To find the smallest integer for $f(x)$, we can use the Fundamental Theorem of Algebra which states that every non-constant polynomial with complex coefficients has at least one complex root. In this case, we are looking for an integer root since we want $65$ to divide $f(x)$ for every integer $x$.

Using this theorem, we can set $f(x)$ equal to $0$ and solve for $x$ to find the integer root. In this case, we have $5x^{13}+13x^5+9\cdot a \cdot x = 0$. This can be simplified to $x(5x^{12}+13x^4+9\cdot a) = 0$. Since we are looking for the smallest integer, we can set $x = 1$ to get $5+13+9\cdot a = 0$. Solving for $a$, we get $a = -2$.

Therefore, the smallest integer for $f(x)$ is $a = -2$ which makes $65$ divide $f(x)$ for every integer $x$. This can be checked by plugging in different values for $x$ and seeing if the result is divisible by $65$.