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

AI Thread Summary
The problem involves finding the smallest integer \( a \) such that \( 65 \) divides the polynomial \( f(x) = 5x^{13} + 13x^5 + 9ax \) for all integers \( x \). By analyzing the polynomial modulo \( 5 \) and \( 13 \), it is determined that \( a \equiv 3 \mod 5 \) and \( a \equiv 11 \mod 13 \). Using the Chinese Remainder Theorem, the smallest positive solution for \( a \) is found to be \( 63 \). Alternatively, the smallest absolute value for \( a \) is \( -2 \), but the focus is on the positive integer. The discussion concludes with an emphasis on the clarification that the smallest positive integer was the intended solution.
lfdahl
Gold Member
MHB
Messages
747
Reaction score
0
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$.
 
Mathematics news on Phys.org
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]
 
Last edited:
$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
 
Last edited:
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:

\[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$$
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Back
Top