Evaluate that polynomial!

Algebra Level 4

Consider all polynomials f ( x ) f(x) with integer coefficients, such that f ( n ) f(n) is a multiple of n n , for all integers 1 n 6 1 \leq n \leq 6 . What is the smallest possible positive value of f ( 0 ) f(0) ?


The answer is 60.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

65 solutions

Reilton Bernardes
Jul 28, 2013

Since that f ( n ) = n p ( n ) + f ( 0 ) f(n) = np(n)+ f(0) and n f ( n ) n|f(n) , so n f ( 0 ) n|f(0) for 1 n 6 1\le n \le 6 . Therefore, f ( 0 ) = k L C M ( 1 , 2 , 3 , 4 , 5 , 6 ) = 60 k f(0)=k*LCM(1,2,3,4,5,6)=60k . Then, the smallest positive value is when k = 1 k=1 and we have: f ( 0 ) = 60 f(0)=60

Moderator note:

I agree that this is nicely done :)

As a clarification, p ( n ) p(n) is the dividend when f ( n ) f(n) is divided by n n .

Nicely done!

Piyal De - 7 years, 10 months ago

Log in to reply

Thanks

Reilton Bernardes - 7 years, 10 months ago

Impressive and easy to understand !

Priyansh Sangule - 7 years, 10 months ago

What was your reason for writing the first statement? How did you get f ( 0 ) f(0) as the remainder?

Ananay Agarwal - 5 years, 9 months ago

U r right, but function is not defined for value 0 it is only mention for 1 to 6, close interval.

rubin agrawal - 5 years, 2 months ago

why did you take it's lcm to find f(0)

A Former Brilliant Member - 4 years, 9 months ago

why 2 can't be the answer consider the polynomial x^2-x+2,when n=2

sakshi rathore - 5 years, 9 months ago

Log in to reply

The polynomial must be a multiple of n for all integers 1≤n≤6, as stated in the problem

pickle lamborghini - 5 years, 7 months ago
Jimmy Kariznov
Jul 28, 2013

Well known result:

For any polynomial f ( x ) f(x) with integer coefficients, f ( x ) f ( y ) f(x) - f(y) is divisible by x y x-y for all integers x , y x,y .

Thus, f ( n ) f ( 0 ) f(n) - f(0) is divisible by n 0 = n n - 0 = n for all n 1 , 6 n \in \overline{1,6} .

But, since f ( n ) f(n) is divisible by n n , we have f ( 0 ) f(0) is divisible by n n for all n 1 , 6 n \in \overline{1,6} .

Hence, f ( 0 ) f(0) must be divisible by lcm { 1 , 2 , 3 , 4 , 5 , 6 } = 2 2 3 5 = 60 \text{lcm}\{1,2,3,4,5,6\} = 2^2 \cdot 3 \cdot 5 = 60 .

So, if f ( 0 ) f(0) is positive, then we must have f ( 0 ) 60 f(0) \ge 60 .

The polynomial f ( x ) = 60 f(x) = 60 has integer coefficients, satisfies the condition that f ( n ) = 60 f(n) = 60 is divisible by n n for all n 1 , 6 n \in \overline{1,6} , and has f ( 0 ) = 60 f(0) = 60 .

Therefore, the smallest possible positive value of f ( 0 ) f(0) is infact 60 \boxed{60} .

Moderator note:

Great approach!

why f(0) is not equal zero ? is so f(n)-f(0) is divisible also by n

King George - 7 years, 10 months ago

Log in to reply

The question asks for the smallest positive value for f ( 0 ) f(0) .

Sreejato Bhattacharya - 7 years, 10 months ago

Sorry for being noob but does the top bar over two numbers separated by a comma represent a list of integers?

Romain Farthoat - 4 years, 11 months ago

@Brilliant Mathematics , I upvoted a Brilliant, but it still shows 0 Brilliant and it is selected:

Vinayak Srivastava - 2 months, 1 week ago

Log in to reply

Thanks for finding this bug. I've forwarded this to the engineers.

Brilliant Mathematics Staff - 2 months, 1 week ago
Owen Mireles
Jul 28, 2013

Be f ( x ) = a 0 x n + a 1 x n 1 + . . . + a n f(x) = a_0x^{n} + a_1x^{n-1} + ... + a_n , such that every a i a_i is an integer. Also, f ( 0 ) = a n f(0) = a_n , and 1 1 divides f ( k ) f(k) for every integer k k .

We know that:

  • 2 f ( 2 ) = a 0 2 n + a 1 2 n 1 + . . . + a n 2 a n 2 | f(2) = a_02^{n} + a_12^{n-1} + ... + a_n \iff 2 | a_n
  • 3 f ( 3 ) = a 0 3 n + a 1 3 n 1 + . . . + a n 3 a n 3 | f(3) = a_03^{n} + a_13^{n-1} + ... + a_n \iff 3 | a_n
  • 4 f ( 4 ) = a 0 4 n + a 1 4 n 1 + . . . + a n 4 a n 4 | f(4) = a_04^{n} + a_14^{n-1} + ... + a_n \iff 4 | a_n
  • 5 f ( 5 ) = a 0 5 n + a 1 5 n 1 + . . . + a n 5 a n 5 | f(5) = a_05^{n} + a_15^{n-1} + ... + a_n \iff 5 | a_n
  • 6 f ( 6 ) = a 0 6 n + a 1 6 n 1 + . . . + a n 6 a n 6 | f(6) = a_06^{n} + a_16^{n-1} + ... + a_n \iff 6 | a_n

So, a n a_n is a positive multiple of 2 , 3 , 4 , 5 , 2, 3, 4, 5, and 6 6 . To minize a n a_n , we find the least common multiple of these numbers. Therefore, the answer is 60 60 .

Very good approach !

Priyansh Sangule - 7 years, 10 months ago

This is the same method I used!

Rishav Koirala - 4 years, 11 months ago
Donny Passary
Jul 28, 2013

Note that f ( 0 ) f(0) is equal to the constant coefficient of the polynomial. And since all the other terms of polynomial will always be multiples of n n when substitute x x with n n , the problem is equivalent to finding the positive least common multiple of 1 , 2 , . . . , 6 1,2,...,6 , which is 60 60 .

Moderator note:

This solution only states a necessary condition, and not a sufficient one.

For completeness, you have to state a polynomial which satisfies the conditions.

Thomas Beuman
Jul 29, 2013

A general expression for f ( x ) f(x) is

f ( x ) = a m x m + a m 1 x m 1 + + a 1 x + a 0 f(x) = a_m x^m + a_{m-1} x^{m-1} + \ldots + a_1 x + a_0 ,

with a 0 = f ( 0 ) a_0 = f(0) . We can rewrite this as

f ( x ) = ( a m x m 1 + a m 1 x m 2 + + a 1 ) x + a 0 f(x) = (a_m x^{m-1} + a_{m-1} x^{m-2} + \ldots + a_1)x + a_0 ,

from which we see that n n divides f ( n ) f(n) iff n n divides a 0 a_0 . Therefore, for f ( n ) f(n) to be divisible by n n for all 1 n 6 1 \leq n \leq 6 , a 0 = f ( 0 ) a_0 = f(0) must be divisible by all n n . The smallest such positive number is f ( 0 ) = 60 f(0) = \boxed{60} .

Avi Swartz
Jul 28, 2013

Let f ( n ) = n × q ( n ) + a f(n)=n \times q(n) +a .

n n must divide f ( n ) f(n) . That can be expressed as f ( n ) n = q ( n ) + a n \frac{f(n)}{n}=q(n)+\frac{a}{n} . Therefore n n must divide a a for all values of n n . The smallest such a a is the lcm of the numbers 1-6. That is 60.

As f ( n ) f(n) is multiple of n then f ( 0 ) f(0) [constant terms] must be multiple of n. The smallest possible positive value of f ( 0 ) f(0) is the LCM of the integers 1 , 2 , 3 , 4 , 5 , 6 1,2,3,4,5,6 ,which is 60 60 .

Michal Forišek
Jul 29, 2013

For any polynomial f f with integer coefficients and any integers m , n m,n : m n m-n must divide f ( m ) f ( n ) f(m)-f(n) . (This easily follows from the fact that m n m-n divides m k n k m^k-n^k for any k 0 k\geq 0 .)

In our problem it follows that for each 1 n 6 1\leq n\leq 6 : f ( n ) f ( 0 ) f(n)-f(0) must be divisible by n n . And as each f ( n ) f(n) is divisible by n n , f ( 0 ) f(0) must be divisible by each of the numbers 1 through 6.

The least common multiple of these numbers is 60 \fbox{60} . The constant polynomial f ( x ) = 60 f(x)=60 shows that this value can indeed be obtained as f ( 0 ) f(0) .

Pi Han Goh
Jul 28, 2013

Let f ( x ) = a n x n + a n 1 x n 1 + a n 2 x n 2 + + a 1 x + a 0 f(x) = a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \ldots + a_1 x + a_0 , with integer a n , a n 1 , a n 2 , , a 1 , a 0 a_n, a_{n-1}, a_{n-2}, \ldots , a_1, a_0

Then f ( x ) = x ( a n x n 1 + a n 1 x n 2 + a n 2 x n 3 + + a 1 ) + x 0 f(x) = x ( a_n x^{n-1} + a_{n-1} x^{n-2} + a_{n-2} x^{n-3} + \ldots + a_1 ) + x_0

Since 2 f ( 2 ) 2 | f(2) , and f ( 2 ) f(2) is simply a scalar multiple of 2 2 plus a 0 a_0 . Then 2 a 0 2 | a_0

Similarly, since Since 2 f ( 2 ) 2 | f(2) , and f ( 2 ) f(2) is simply a scalar multiple of 3 3 plus a 0 a_0 . Then 3 a 0 3 | a_0

Using the same analogy, we can prove that 4 a 0 , 5 a 0 , 6 a 0 4 | a_0, 5 | a_0, 6 | a_0

Thus a 0 a_0 is divisible by 1 , 2 , 3 , 4 , 5 , 6 1,2,3,4,5,6 . So the smallest positive value of f ( 0 ) f(0) is l c m ( 1 , 2 , 3 , 4 , 5 , 6 ) = 2 2 × 3 × 5 = 60 lcm(1,2,3,4,5,6) = 2^2 \times 3 \times 5 = \boxed{60}

Typo: " Similarly, since 3 f ( 3 ) 3|f(3) , and f ( 3 ) f(3) is simply a scalar multiple of 3 3 plus a 0 a_0 . Then 3 a 0 3|a_0 "

Pi Han Goh - 7 years, 10 months ago
Lucas Reis
Jul 28, 2013

We have a b f ( a ) f ( b ) a-b|f(a)-f(b) for all p ( x ) p(x) polynomial with integers coeficients.

So n f ( n ) , 1 n 6 n 0 f ( n ) f ( 0 ) n f ( 0 ) , 1 n 6 n|f(n), \forall 1\le n\le 6\Rightarrow n-0|f(n)-f(0)\Rightarrow n|f(0), \forall 1\le n\le 6

and then 60 = l c m ( 1 , 2 , . . . , 6 ) f ( 0 ) f ( 0 ) 60 60=lcm(1, 2, ..., 6)|f(0)\Rightarrow f(0)\ge 60 since that f ( 0 ) > 0 f(0)>0 .

Actually, f ( x ) = 60 f(x)=60 satisfies n f ( n ) , 1 n 6 n|f(n), \forall 1\le n\le 6 and f ( 0 ) = 60 f(0)=60 .

Raza Agha
Jul 30, 2013

For a number to be multiple of 1,2,3,4,5,6, it only needs to be a multiple of 3,4 and 5. Why? Why not 1,2 and 6. Because every number is a multiple of 1, and 2 is already contained in a 4 (4=2x2) and 6 is also contained ( and this is a little less obvious) in a 3 and 4. Because 6=2x3 and 4=2x2 and 4x3= 2x(2x3)= 2x6 =12. therefore that 4x3 is a multiple of 6. How do we find the numbers needed to create a multiple of every number. Well all we do is prime factorization of every number. Therefore 1,2,3,4,5,6 is equal to 1,2,3,2x2,5,2x3. Next we choose the number of different numbers we see. We have to choose a 5, a 3 and two 2's because 4 contains two 2's and for a number to be a multiple we must choose two 2's. Therefore the number we choose is 5x3x2x2=60. Now f(n) is a multiple of 60. Therefore all the integer coeffiencents of f(n) are multiples of 60. But we are interested in f(0) namely the constant term. For f(n) to be a multiple of 60 either the constant term is zero (it doesm't exist) or its a multiple of 60. The question says us to find the smallest possible positive value. 0 is not positive, and the smallest value is 60. Therfore 60 is the answer.

Abhishek Mondal
Jul 30, 2013

constant term has to be divisible by n such that 1<=n<=6. LCM of all possible n's i.e 1,2,3,4,5,6 is 60. f(0) always indicates the constant term. So, the smallest possible value of f(0) is 60

Harrison Lian
Jul 29, 2013

Let f ( x ) = a 1 x n + a 2 x n 1 + a 3 x n 2 . . . + a k f(x)=a_1x^n+a_2x^{n-1}+a_3x^{n-2}...+a_k .

Clearly, a 1 x n + a 2 x n 1 + a 3 x n 2 . . . a_1x^n+a_2x^{n-1}+a_3x^{n-2}... is divisible by n n because n n is in it. That means that the last term, a k a_k must be divisible by the numbers 1 , 2 , 3..6 1,2,3..6 . This is simply the least common multiple of 1 , 2 , 3..6 1,2,3..6 , which is 60 60 . Plug in n = 0 n=0 to get f ( 0 ) = 60 \boxed{f(0)=60} .

Oops, I meant x=0

Harrison Lian - 7 years, 10 months ago
Michael Tang
Jul 29, 2013

Let f ( x ) = a i x i + a i 1 x i 1 + + a 1 x + a 0 f(x) = a_ix^i + a_{i-1}x^{i-1} + \ldots + a_1x + a_0 (the general form of a polynomial), so that f ( 0 ) = a 0 . f(0) = a_0. Then we have that f ( n ) = a i n i + a i 1 n i 1 + + a 1 n + a 0 f(n) = a_in^i + a_{i-1}n^{i-1} + \ldots + a_1n + a_0 is a multiple of n , n, for n = 1 , 2 , , 6. n = 1, 2, \ldots, 6. Because a 0 , a 1 , , a i a_0, a_1, \ldots, a_i are integers, we note that all terms of the above sum, except for a 0 , a_0, are already multiples of n . n. Thus it must be the case that f ( 0 ) = a 0 f(0) = a_0 is a multiple of n n for n = 1 , 2 , , 6. n = 1, 2, \ldots, 6.

So, we want the smallest multiple of 1 , 2 , 3 , 4 , 5 , 6 , 1, 2, 3, 4, 5, 6, which is lcm ( 1 , 2 , 3 , 4 , 5 , 6 ) = 60. \text{lcm}(1, 2, 3, 4, 5, 6) = 60. The smallest positive value of f ( 0 ) f(0) is 60 . \boxed{60}.

Tim Vermeulen
Jul 29, 2013

In order for f ( n ) f(n) to be a multiple of n n , the constant term ( which is f ( 0 ) ) \left(\text{which is }f(0)\right) must be a multiple of n n , because all other terms are a multiple of n n . So, the smallest possible positive value of f ( 0 ) f(0) is the least common multiple of the integers 1 , 2 , 3 , 4 , 5 , 6 1,2,3,4,5,6 , which is 60 \boxed{60} .

Aditya Parson
Jul 29, 2013

We let f ( x ) = a 1 x n + a 2 x n 1 + . . . . . + a n f(x)= a_1 x^n + a_2 x^{n-1} +.....+ a_n where a 1 , a 2 , . . . . , a n 0 a_1, a_2,...., a_n \neq 0 are integers.

If we substitute for n n it is clear that all the terms except the constant term( a n a_n ) will be divisible by n n . Hence, we must have that a n a_n is a multiple of n n .

Since a n a_n must be divisible by all 1 n 6 1 \leq n \leq 6 in the range then to minimize f ( 0 ) f(0) we minimize a n a_n .

Thus, the least possible value of a n = l c m ( 1 , 2 , 3 , 4 , 5 , 6 ) = 60 a_n= lcm(1,2,3,4,5,6)=60

Hence least possible value of f ( 0 ) = 60 f(0)= \boxed{60}

It's much more convenient if you match the coefficient a k a_k with x k x^k . You did the reverse, which lead to a mistake: it should be a n x + a n + 1 a_{n}x+a_{n+1} , rather than just a n a_n . Also, not all coefficients have to be nonzero.

Tim Vermeulen - 7 years, 10 months ago
Ankan Gope
Jul 29, 2013

Every thing in the polynomial should be divisible by n since we put n in place of x, except the constant in the expression. Hence, to be divisible, the constant must also be divisible by all integers from 1 to 6. Therefore the constant must be the L.C.m of 1,2,3,4,5, and 6 = 60. Hence, the answer is 60.

Albert Pranata
Jul 29, 2013

Write f ( x ) = x n + a 1 x n 1 + . . . + a n 1 x + a n f(x)=x^n+a_1x^{n-1}+...+a_{n-1}x+a_n with a i ; i = 1 , 2 , 3 , . . . , n a_i;i=1,2,3,...,n is an integer. From here, we can conclude that x f ( x ) a n x|f(x)-a_n . But, we know that x f ( x ) x|f(x) for all integers 1 x 6 1\leq x\leq6 . So, x a n x|a_n for all integers 1 x 6 1\leq x\leq6 . Since f ( 0 ) = a n f(0)=a_n , the minimal positive value of f ( 0 ) f(0) is L C M ( 1 , 2 , 3 , 4 , 5 ) LCM(1,2,3,4,5) which is equal with 60 60 . So, the answer is 60 60 .

Raymond Lin
Jul 28, 2013

A polynomial f ( x ) f(x) can be written in the form a i x i + a i 1 x i 1 + a i 2 x i 2 + . . . a 1 x + a 0 a_ix^i+a_{i-1}x^{i-1}+a_{i-2}x^{i-2}+...a_{1}x+a_{0} , so f ( n ) = a i n i + a i 1 n i 1 + . . . a 1 n + a 0 f(n)=a_in^i+a_{i-1}n^{i-1}+...a_{1}n+a_{0} , or n ( a i n i 1 + a i 1 n i 2 + . . . a 1 ) + a 0 n(a_in^{i-1}+a_{i-1}n^{i-2}+...a_1)+a_0 . Since n ( a i n i 1 + a i 1 n i 2 + . . . a 1 ) n(a_in^{i-1}+a_{i-1}n^{i-2}+...a_1) is clearly a multiple of n n , for n n to divide f ( n ) f(n) , a 0 a_0 must be a multiple of n n . Therefore, for n n to divide f ( n ) f(n) for n n from 1 1 to 6 6 , a 0 = l c m ( 1 , 2 , 3 , 4 , 5 , 6 a_0=lcm(1, 2, 3, 4, 5, 6 =60). f ( 0 ) f(0) is clearly just a 0 a_0 , so our answer is 60 \fbox{60} .

Alexander Maly
Jul 28, 2013

f(n)-f(0) always divides by n, so f(0) should divide by lcm(1, 2, 3, 4, 5, 6)=60
Polinom f(n)=60 works.

f(1)= a 1×1^n+a 2×1^(n-1)+..+a n×1 thus a n must be divisible by 1 f(2)= a 1×2^n+a 2×2^(n-1)+..+a n×2^0 thus a n must be divisible by 2 f(3)= a 1×3^n+a 2×3^(n-1)+..+a n×3^0 thus a n must be divisible by 3 f(4)= a 1×4^n+a 2×4^(n-1)+..+a n×4^0 thus a n must be divisible by 4 f(5)= a 1×5^n+a 2×5^(n-1)+..+a n×5^0 thus a n must be divisible by 5 f(6)= a 1×6^n+a 2×6^(n-1)+..+a n×6^0 thus a n must be divisible by 6 Then a n must be divisible by 1,2,3,4,5,6 then the GCD=60,then the smallest a n must be 60 then f(0)= a 1×0^n+a 2×0^(n-1)+..+a n×0^0 thus a 1×0^n+a 2×0^(n-1)+..+a (n-1)×0^1=0 then f(0)=60

Danny He
Aug 3, 2013

For any polynomial with integer coefficients, f ( n ) = a 0 n 0 + a 1 n 1 + a 2 n 2 + . . . + a k n k f\left(n\right) = a_0n^0 + a_1n^1 + a_2n^2 + ... + a_kn^k

If n n is to be a divisor of f ( n ) f\left(n\right) for 1 n 6 1\leq n\leq6 then it is clear a 0 a_0 is divisible by 1 , 2 , 3 , 4 , 5 , 6 1,2,3,4,5,6 . The smallest such positive integer is therefore 1 2 2 3 5 = 60 1*2*2*3*5 = 60

Connor Harris
Aug 1, 2013

Write f ( x ) = a k x k + a k 1 n k 1 + + a 1 n + a 0 f(x) = a_k x^k + a_{k-1} n^{k-1} + \ldots + a_1 n + a_0 , with a i Z a_i \in \mathbb{Z} for all 0 i k 0 \leq i \leq k . If n n divides f ( n ) f(n) , then as n n divides all the terms on the right-hand side of the previous expression except a 0 a_0 , n n must also divide a 0 a_0 . Thus, a 0 a_0 is a common multiple of all the integers 1 1 through 6 6 , and the least such common multiple is 60 60 ; as f ( 0 ) = a 0 f(0) = a_0 , this solves the problem.

Whoops - that should be x instead of n throughout the first equation.

Connor Harris - 7 years, 10 months ago
Allegra Zocchi
Aug 1, 2013

Because any multiple of n n added to another multiple of n n is also a multiple of n n , we can assume that for all integers n n , f ( n ) f(n) is a multiple of n n as long as there is no constant term in f ( x ) f(x) (i.e., such that the coefficient is multiplied by n 0 n^0 ).

The problem states that f ( n ) f(n) must be a multiple of n n for all integers 1 n 6 1 \leq n \leq 6 . Zero is not positive, so the solution can't be f ( 0 ) = 0 f(0) = 0 . For any polynomial, f ( 0 ) = 0 + f(0) = 0 + any constants in the polynomial. Again, because any multiple of n plus another multiple of n is a multiple of n as well, in order for f(n) to be a multiple of n n for n = 1 , 2 , 3 , 4 , 5 , 6 n = {1, 2, 3, 4, 5, 6} , the constant must be a multiple of all these integers. We are looking for the smallest possible value of n, so the problem is simply to find the lcm(1, 2, 3, 4, 5, 6):

lcm(1, 2) = 2

lcm(2,3) = 6

lcm (6, 4) = 12

lcm (6, 5) = 60

lcm(1, 2, 3, 4, 5, 6) = 60
Tan Yee Jian
Aug 1, 2013

As given in the question, all coefficients are in integer value, that means it is a multiple of n; to let the funcion be a multiple of n, the constant must also be the multiple of n.

We know that during f(0), all terms with x have the same value 0.

Then, the only positive value is from the constant.

The value of the constant = L.C.M. of (2, 3, 4, 5, 6) = 30

Then f(0) = 30

Sorry : the Lowest Common Multiple of (2,3,4,5,6) equals to 60 So f(0) = 60

Tan Yee Jian - 7 years, 10 months ago
Rindell Mabunga
Aug 1, 2013

For every polynomial x, all terms except the last term is divisible by powers of x. Therefore if n divides f(n) for every integer n less greater than or equal to 1 and less than equal to 6, then n must divide the last term of f(x). Getting the LCM of 1, 2, 3, 4, 5, and 6, we will get 60 which is the smallest positive value of f(0) or in other words the last term

Russell Few
Aug 1, 2013

We let the polynomial be a k x k + a n 1 x n 1 + . . . + a 1 a_kx^k+a_{n-1}x^{n-1}+...+a_1 . It is given that a 1 , a 2 , . . . , a k a_1, a_2, ..., a_k are integers. For integer k k where 1 i k 1 \le i \le k , all of a i x i a_ix^i is divisible by n n . Hence, since f ( n ) f(n) is a multiple of n n , it is then required that a 1 a_1 is divisible by all of 1 , 2 , 3 , 4 , 5 , 6 1, 2, 3, 4, 5, 6 . Hence n n must be a multiple of the least common multiple of 1 , 2 , 3 , 4 , 5 , 6 1, 2, 3, 4, 5, 6 , which is 60 60 . Thus, the smallest possible positive value of f ( 0 ) f(0) is 60 \boxed{60} .

Yong Daniel
Aug 1, 2013

tle LCM (lowest common multiple) from 1 to 6 is 60

Albert Ho
Jul 31, 2013

All the non-constant terms of a polynomial f ( x ) f(x) have a variable such that those terms will be a multiple of whatever n n is when n n is plugged in as the variable. Thus, the only term that determines whether or not f ( n ) f(n) is a multiple of n n is the constant term. The LCM of the integers 1-6 is 60, since the next smallest value that works is zero, 60 is the smallest positive value that works.

Kyle Kibodeaux
Jul 31, 2013

LCM 1,2,3,4,5,6 = 60

Kevin Limanta
Jul 31, 2013

Let f ( x ) f(x) be a polynomial of order m m , that is f ( x ) = a 0 + a 1 x + a 2 x 2 + + a m x m f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_mx^m . Notice that if n f ( n ) n \mid f(n) , then n a 0 n \mid a_0 . Because n f ( n ) n \mid f(n) for 1 n 6 1 \le n \le 6 , then we have n a 0 n \mid a_0 for 1 n 6 1 \le n \le 6 . The smallest a 0 a_0 therefore is a 0 = lcm ( 1 , 2 , 3 , 4 , 5 , 6 ) = 60 a_0 = \text{lcm}(1, 2, 3, 4, 5, 6) = 60 .

Note first that if we write f ( x ) = a k x k + + a 1 x + a 0 f(x) = a_k x^k + \ldots + a_1 x + a_0 , then f ( 0 ) = a 0 f(0) = a_0 .

We are given that for 1 n 6 1 \leq n \leq 6 , n f ( n ) n | f(n) . Since for each integer n n we also have n a k n k + + a 1 n n | a_k n^k + \ldots + a_1 n , we conclude that n a 0 n | a_0 .

It's easy to check that the smallest positive integer that divides n n for all 1 n 6 1 \leq n \leq 6 is 60 60 and that any polynomial with integer coefficients where a 0 = 60 a_0 = 60 will satisfy the requirements.

Since f ( x ) f(x) is a polynomial with integer coefficients, it follows that n ( f ( 0 ) f ( n ) ) n \mid (f(0)-f(n)) for all positive integers n . n. From the assumption, we have n f ( n ) n \mid f(n) for 1 n 6. 1 \le n \le 6. Therefore n ( f ( n ) + ( f ( 0 ) f ( n ) ) or n f ( 0 ) n \mid (f(n)+(f(0)-f(n)) \quad \text{or} \quad n\mid f(0) for 1 n 6. 1\le n \le 6. This implies f ( 0 ) f(0) is a common multiple of the integers 1 , 2 , , 6. 1,2,\dots,6. Hence the smallest possible positive value of f ( 0 ) f(0) is the least common multiple of the integers 1 , 2 , , 6 1,2,\dots,6 , namely 60 . \boxed{60}.

f ( n ) = i = 0 a i n i = k n n , k , a Z , 0 < n < 7 f(n)=\sum_{i=0}^{\infty}{a_i n_i}=k n \;\forall n,k,a\in\mathbb{Z},0<n<7 .

As all the sum terms of order n n or higher are divisible by n n , and the sum itself is divisible by n n , it implies that a 0 a_0 is also divisible by n n . As f ( 0 ) = a 0 f(0)=a_0 , we seek the minimal positive value of a 0 a_0 , which is l c m ( 1 , 2 , 3 , 4 , 5 , 6 ) = 60 \mathrm{lcm}(1,2,3,4,5,6)=60 .

since you have f(x)=a1x^n+a2x^(n-1)....+a (n-2)+a (n-1)x+a n= x[a1x^(n-1+a2x^(n-2)....+a (n-2)x+a (n-1)]+a n, we have f(x) = a_n mod x. So, the constant term has to be divisible by all integer n in [1,6]. The least common multiple of all of these is 60. Since f(0) is the constant term, f(0)=60

Sushmita Nad
Jul 31, 2013

its the LCM of all numbers between 1 to 6 = 60...

Albert Gav
Jul 30, 2013

f(x)>= LCM {1,2,3,4,5,6}=60

the min f(x)=60

David Nolasco
Jul 30, 2013

The polynomial f ( x ) f(x) , to have the smallest possible value of f ( 0 ) f(0) , should have a constant K which is the LCM of (1,6).

Since all the terms with the powers of x will cancel in f ( 0 ) f(0) , the smallest possible value of f ( 0 ) f(0) is the LCM (1,6) which is 60.

Steven Yang
Jul 30, 2013

To find f ( 0 ) f(0) implies finding the value of the constant in the polynomial. Since any term carrying the variable n n will essentially be a multiple of n n , the smallest possible value of f ( 0 ) f(0) will be the LCM of 1 , 2 , 3 , 4 , 5 , 6 1,2,3,4,5,6 , namely 60 60 .

Evan Chien
Jul 30, 2013

The LCM of 1 to 6 is 60

Jeffery Yu
Jul 30, 2013

It is well known that if a b a|b and a b + c a|b+c , then a c a|c . We have that for all 1 n , n f ( n ) 1 \le n \le, n|f(n) . We express f ( x ) f(x) as a general polynomial: a k x k + a k 1 x k 1 + . . . + a 1 x + a 0 a_kx^k + a_{k-1}x^{k-1} + ... + a_1x + a_0 . Consider all the nonconstant terms (ie: all the terms except a 0 a_0 ). They are always divisible by x x because the coefficients are given to be integers. Since n f ( n ) n|f(n) and n n divides all the nonconstant terms, we must also have n a 0 n|a_0 . Thus, a 0 a_0 has to be a multiple of all n n between 1 1 and 6 6 . The least possible a 0 a_0 is L C M ( 1 , 2 , 3 , 4 , 5 , 6 ) = 60 LCM(1, 2, 3, 4, 5, 6) = \boxed{60}

Sorry the start of the second line should read 1 n 6 1 \le n \le 6

Jeffery Yu - 7 years, 10 months ago
Ahaan Rungta
Jul 30, 2013

We have f ( x ) = g ( x ) + c f(x) = g(x) + c , where g g is a polynomial divisible by x x and c c is an integer constant. The problem boils down to finding the smallest possible positive value of c c that is divisible by all integers 1 n 6 1 \le n \le 6 .

This is just lcm ( 1 , 2 , 3 , 4 , 5 , 6 ) = 60 \text {lcm}(1,2,3,4,5,6) = \boxed {60} .

Michael Tong
Jul 30, 2013

f(0) is equal to the constant value of the function. If f(n) = n, then the first statement holds, but then f(0) is not positive. So, we need to find gcd(1, 2, 3, 4, 5, 6). This is 60. We know this is the lowest value because if we increase the degree, we will at least be finding the g c d ( 1 , 2 d , 3 d , 4 d , 5 d , 6 d ) gcd(1, 2^d, 3^d, 4^d, 5^d, 6^d) . So, f ( 0 ) = 60 f(0) = 60

We note, f(n) is always divisible by n if there is no constant term. However, this implies f(0) = 0 which is not a positive value. So the constant term must be divisible by all integers from 1 to 6 so that f(n) is divisible by n.

Again, this constant term is to be minimum so we take the LCM of those integers from 1 to 6. We obtain the constant term as 60.

Benson Li
Jul 29, 2013

Consider a polynomial F ( n ) F(n) which does not have a constant term. Then, the number F ( n ) F(n) must have n as factor, which implies F ( n ) F(n) is a multiple of n. This further implies that for the given function f ( n ) f(n) to be a multiple of 1 6 1-6 , the constant term must be a multiple of all six numbers. The smallest possible value of this is the absolute value of the L C M LCM , which can be deduced from the prime factorization of the six numbers. Taking the positive number, we get L C M = 60 LCM=60

Daniel Liu
Jul 29, 2013

Note that except for the constant term, every other term of f(n) is a multiple of (n). Therefore, for f(x) to be a multiple of x where x is 1--6, we need the constant term to be a multiple of all of 1--6. That number is 60 60 .

Felipe Siqueira
Jul 29, 2013

f(0) = LCM(1,2,3,4,5,6) = 60

Rodrigo Fischer
Jul 29, 2013

Imagine the polynomial is a first degree one. Now you are at a huge numbered line where you start on "b" if a x + b = k a \cdot x + b = k . You walk to get to a desired point, and the amout you walk is a x a \cdot x , the point you will end up is f(x). If x is one, f(x) will always be a multiple of one. If x is two, it will walk a 2 a \cdot 2 , so you must start on a even number. If x is three, you will walk a 3 a \cdot 3 , a multiple of three, so, you must start on a multiple of three aswell, to the left or to the right, depending on "a". So "b" must be a multiple of 1, 2, 3, 4, 5 and 6. Since it wants the smallest possible "b", it will be the least common multiple of these numbers.

Yue Zhang
Jul 29, 2013

Consider a general polynomial a 1 x n + a 2 x n 1 + a 3 x n 2 + . . . a_1 x^n + a_2 x^{n-1} + a_3 x^{n-2} + ... .

In the problem statement, it is known that for 1 n 6 1 \le n \le 6 n divides the polynomial. However notice that all terms except for the constant term of the polynomial includes powers of n and are divisible by n. Thus only the constant term determines whether the polynomial is divisible by the numbers.

Since all numbers between 1 and 6 divide the constant term, it must be multiples of their LCM, or multiples of 60. Note that f(0) is the constant term. Hence the smallest possible value of it is 60.

Jubayer Nirjhor
Jul 29, 2013

Pretty simple... Is there any need to explain??? The answer is,

L C M ( 1 , 2 , 3 , 4 , 5 , 6 ) = 60 LCM(1,2,3,4,5,6) = 60

The End...

The polynomial f ( x ) f(x) has a term independent of x x , and this is multiple of 1 1 , 2 2 , 3 3 , ..., 6 6 . So its minimum positive value must be 2 3 2 5 = 60 2\cdot 3\cdot 2\cdot 5=60 , so the minimum positive value of f ( 0 ) f(0) is 60 60

Prince Loomba
Jul 9, 2016

I just assumed f(x) to be constant.60 satisfies the value. But by this method it cant be proved that 60 is smallest value for f (0)

Sebastian Garrido
Jul 29, 2013

For any polynomial, n|f(n) if n divides each term in the polynomial. It naturally divides each term where the exponent of x is different from 0, therefore we must look for a constant term that is minimal, positive and divisible by all n from 1 to 6. This is the lcm(1,2,3,4,5,6)=60.

Advitiya Brijesh
Jul 29, 2013

Let the polynomial be f ( x ) = a 0 + a 1 x + + a m x m f(x)=a_0 + a_1 x + \cdots + a_m x^m , if f ( n ) f(n) is multiple of n n then it must be divisible by n n . So, f ( n ) = a 0 + a 1 n + + a m n m f(n)=a_0 + a_1 n + \cdots + a_m n^m . From, f ( n ) f(n) we can see that a 1 n + a 2 n 2 + + a m n m a_1 n+a_2 n^2 +\cdots + a_m n^m is divisible by n n so we need to see the divisibility of a 0 a_0 . As, question seeks for smallest positive values of f ( 0 ) f(0) so it will obviously be equal to L.C.M. o f 1 , 2 , 3 , 4 , 5 , 6 \text{L.C.M.} of 1, 2, 3, 4, 5, 6 which is equal to 60 \boxed{60}

Mayank Kaushik
Jul 29, 2013

L C M o f ( 1 , 2 , 3 , 4 , 5 , 6 ) = 60 LCM of (1,2,3,4,5,6) = 60

Dewei Chen
Jul 29, 2013

To make the value of f(n) as small as possible, we let f(n)=an+a, where a is a positive integer. In that case, f(1) divides 2a, f(2) divides 3a, f(3) divides 4a, f(4) divides 5a, f(5) divides 6a and f(6) divides 7a. By observation, the value of a is minimum when it is lcm(1,2,3,4,5,6), thus a is 60. Then, it follows that f(n)=60n+60. Thus, the smallest possible positive value of f(0) is 60.

Aditya Pappula
Jul 29, 2013

Answer = LCM(1 2 3 4 5 6)

why is it just the LCM of 1,2,3,4,5,6

Spitzer 300 - 7 years, 10 months ago

The question asks for smallest possible value of f ( 0 ) f(0) i.e. constant term of the polynomial. All non-constant terms of f ( x ) f(x) are divisible by x x , n f ( n ) n | f(n) iff n a 0 n | a_0 , the constant term. So required smallest positive term is the LCM of 1 to 6 i.e., 60 60 .

Matt McNabb
Jul 29, 2013

This problem must have fallen through from level 2...:)

All terms in a polynomial are powers of n n , except the constant term. Since the coefficients are integers, n n must divide all of the non-constant terms. Therefore, if n n divides f ( n ) f(n) , then n n must divide the constant term.

So the smallest possible positive constant term is the LCM of ( 1 , 2 , 3 , 4 , 5 , 6 ) (1, 2, 3, 4, 5, 6) , i.e. 60 60 .

Zi Song Yeoh
Jul 28, 2013

Let f ( x ) = a n x n + a n 1 x n 1 + . . . + a 0 f(x) = a_{n}x^{n} + a_{n - 1}x^{n - 1} + ... + a_{0} .  Note that f ( 0 ) = a 0 f(0) = a_{0} . Note that for f ( x ) f(x) to satisfy the problem condition, a 0 a_{0} must be a multiple of 1 , 2 , 3 , 4 , 5 1, 2, 3, 4, 5 and 6 6 . So, the least positive possible value for f ( 0 ) = a 0 f(0) = a_{0} is L C M ( 1 , 2 , 3 , 4 , 5 , 6 ) = 60 LCM(1, 2, 3, 4, 5, 6) = 60 .

Debjit Mandal
Jul 28, 2013

Let, the polynomial is
f f ( x x ) = a n a_{n} x n x^{n} + a n 1 a_{n-1} x n 1 x^{n-1} +........+ a i a_{i} x i x^{i} + ........+ a 1 a_{1} x 1 x^{1} + a 0 a_{0} x 0 x^{0} ...............(1)
So,

f f ( 1 1 ) = a n a_{n} + a n 1 a_{n-1} +..........+ a i a_{i} +..........+ a 0 a_{0} .............(2)
f f ( 2 2 ) = a n a_{n} 2 n 2^{n} + a n 1 a_{n-1} 2 n 1 2^{n-1} +........+ a i a_{i} 2 i 2^{i} + ........+ a 1 a_{1} 2 1 2^{1} + a 0 a_{0} ..........(3)
f f ( 3 3 ) = a n a_{n} 3 n 3^{n} + a n 1 a_{n-1} 3 n 1 3^{n-1} +........+ a i a_{i} 3 i 3^{i} + ........+ a 1 a_{1} 3 1 3^{1} + a 0 a_{0} ..........(4)
f f ( 4 4 ) = a n a_{n} 4 n 4^{n} + a n 1 a_{n-1} 4 n 1 4^{n-1} +........+ a i a_{i} 4 i 4^{i} + ........+ a 1 a_{1} 4 1 4^{1} + a 0 a_{0} ..........(5)
f f ( 5 5 ) = a n a_{n} 5 n 5^{n} + a n 1 a_{n-1} 5 n 1 5^{n-1} +........+ a i a_{i} 5 i 5^{i} + ........+ a 1 a_{1} 5 1 5^{1} + a 0 a_{0} ..........(6)
f f ( 6 6 ) = a n a_{n} 6 n 6^{n} + a n 1 a_{n-1} 6 n 1 6^{n-1} +........+ a i a_{i} 6 i 6^{i} + ........+ a 1 a_{1} 6 1 6^{1} + a 0 a_{0} ..........(7)




We know that, for 1 1 \leq n n \leq 6 6 ; f f ( n n ) is a multiple of n n
Then from the R.H.S. of (1), we can find that a 0 a_{0} must be a multiple of n n for only 1 1 \leq (n) \leq 6 6 , not for n n = 0 0 So, the minimum value of a 0 a_{0} should be l c m lcm ( 1 1 , 2 2 , 3 3 , 4 4 , 5 5 , 6 6 ) = 60 60
[ NOTE THAT , a 0 a_{0} can be any integer multiple of 60 60 , but here we need the minimum value ]
When we put x x = 0 0 in (1), then f f ( 0 0 ) = a 0 a_{0} .
So, the smallest possible positive value of f f ( 0 0 ) = 60 60 [ANSWER]



Note that for all n n , n f ( n ) f ( 0 ) n \mid f(n) - f(0) (if f ( n ) = i = 0 p c i n i f(n)= \sum_{i=0}^{p} c_i n^i , f ( 0 ) = c 0 f(0)= c_0 , and hence f ( n ) f ( 0 ) = i = 1 p c i n i = n i = 1 p c i n i 1 f(n) - f(0)= \sum_{i=1}^{p} c_i n^i = n\sum_{i=1}^{p} c_i n_{i-1} ). Since all the integers 1 1 , 2 2 , . . . ... , 6 6 divide f ( n ) f(n) , all of them must divide f ( 0 ) f(0) . Therefore, minimum possible value of f ( 0 ) = l . c . m ( 1 , 2 , 3 , 4 , 5 , 6 ) = 60 f(0)= l.c.m(1, 2, 3, 4, 5, 6)= 60 .

Correction:- i = 1 p c i n i = n i = 1 p c i n i 1 \sum_{i=1}^{p} c_i n^i = n\sum_{i=1}^{p}c_i n^{i-1}

Sreejato Bhattacharya - 7 years, 10 months ago

Note:- this should have been added in my solution, very sorry for omitting it.

The proof of the existence of such a polynomial f ( x ) f(x) is trivial. Any polynomial of the form i = 1 p c i n i + 60 \sum_{i=1}^{p} c_i n^i + 60 (where the c i c_i s are integers) satisfies the given conditions.

Sreejato Bhattacharya - 7 years, 10 months ago
Rik Tomalin
Jul 28, 2013

f(0) must divide all values of n in the given range.

Since f(x) has integer coefficients only, we are certain that all terms in f(n), except the constant term, are divisible by n. Now we only have to make this constant term divisible by n as well and we can do so by choosing it as a common multiple of the numbers in the set {1,2,3,4,5,6}. The minimum value of the constant term, which is obviously equal to f(0), is the LCM of the given set, which is equal to 60.

Jonathan Fang
Jul 28, 2013

Expressing f ( n ) f(n) as a n 2 + b n + c an^2+bn+c for f ( n ) f(n) to be a multiple of n, a n 2 + b n + c 0 ( m o d n ) an^2+bn+c \equiv 0 \pmod{n} . This means that c 0 ( m o d n ) c \equiv 0 \pmod{n} . The restraints given to us by the problem will give us c 0 ( m o d 1 ) c \equiv 0 \pmod{1} , c 0 ( m o d 2 ) c \equiv 0 \pmod{2} , c 0 ( m o d 3 ) c \equiv 0 \pmod{3} , c 0 ( m o d 4 ) c \equiv 0 \pmod{4} , c 0 ( m o d 5 ) c \equiv 0 \pmod{5} , c 0 ( m o d 6 ) c \equiv 0 \pmod{6} . This means that c = u , c = 2 v , c = 3 w , c = 4 x , c = 5 y , c = 6 z c=u, c=2v, c=3w, c=4x, c=5y, c=6z , where u,v,w,x,y, and z are all positive integers. The smallest possible value of c that satisfies all of these equations is 60. f ( 0 ) = 0 2 a + 0 b + 60 = 60 f(0) = 0^2a+0b+60=60

Jonathan why did you assume f to be a quadratic?

Piyal De - 7 years, 10 months ago

Log in to reply

whoops...everything is still the same though from c 0 ( m o d n ) c \equiv 0 \pmod {n} that was really bad...

Jonathan Fang - 7 years, 10 months ago

how can u assume that the polynomial is a quadratic?

Sagnik Saha - 7 years, 10 months ago

Log in to reply

I can't, I made a mistake.

Jonathan Fang - 7 years, 10 months ago
Shashank Goel
Jul 28, 2013

when f(x) is divided by x , the remainder is a constant . so for n= 1,2,3,4,5,6 ,constant term should be lcm of all these terms which is 60

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...