In the expansion of ( 1 + x ) n , for ALL coefficients except those of the first and last terms to be divisible by n , n has to be a/an?
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.
Here's another way to look at it (hopefully my approach isn't flawed):
By the binomial theorem, we know that,
( 1 + x ) n = i = 0 ∑ n ( i n ) x i
We need n such that ( r n ) ≡ 0 ( m o d n ) ∀ 0 < r < n .
( r n ) = r ! ⋅ ( n − i ) ! n ! = r ! 1 ⋅ i = 0 ∏ r − 1 ( n − i ) ⟹ ( r n ) ≡ r ! n i = 1 ∏ r − 1 ( − i ) ( m o d n ) ⟹ ( r n ) ≡ r ! ± n ⋅ ( r − 1 ) ! ≡ r n ( m o d n )
The ± is written to account for both the parity cases of r (odd/even). It doesn't matter though since n ≡ − n ( m o d n ) . Now, for this to be divisible by n , we have,
( r n ) ≡ 0 ( m o d n ) ⟹ r n ≡ 0 ( m o d n ) ⟹ g cd ( r , n ) = 1
Since the problem statement wants that all the coefficients except first and last be divisible by n , we have,
g cd ( r , n ) = 1 ∀ 0 < r < n ⟺ n is a prime number
Observation of Pascal Triangle shows that it is not odd or even nor square number. However 2,3,5, 7 works. Hence the answer after checking for 11 and 13. Yes, This is NOT a proof. I agree.
This solution has been marked wrong because you can't prove by method of exhaustion for an infinite number of cases.
Is there a mathematical solution? If there I'd can you pls show it.
Log in to reply
I have posted a proof based on the binomial expansion theorem for
(
1
+
x
)
n
(also known as the easy case of
Pascal's triangle
)
You can look at the triangle now and see the pattern at work, like the observation solution suggests.
Problem Loading...
Note Loading...
Set Loading...
The problem says to ignore the first and last terms, so assume n ≥ 2 so there are at least 3 terms in the expansion, and 1 ≤ k ≤ ( n − 1 ) . The coefficient of the term x k in the expansion of ( 1 + x ) n is the binomial coefficient c k = ( k n ) = k ! ( n − k ) ! n ! . c k is always an integer since k ! and ( n − k ) ! are factors of n ! , and if n is prime, then n = p , p ∈ P . c k = ( 1 × 2 × . . . × k ) ( 1 × 2 × . . . × ( p − k ) ) 1 × 2 × 3 × . . . × p Assumed above, 1 ≤ k ≤ ( n − 1 ) . Therefore 1 ≤ k ≤ ( p − 1 ) and 1 ≤ ( p − k ) ≤ ( p − 1 ) . Since both terms in the denominator are less than p and p cannot be written as the product of positive integers less than itself, p is not a factor of the denominator. Therefore the quotient above is a multiple of p , or p itself.
On the other hand, in the case where n is a composite number m , c k = ( 1 × 2 × . . . × k ) ( 1 × 2 × . . . × ( m − k ) ) 1 × 2 × 3 × . . . × m There must be at least one k (and its opposite, ( m − k ) , ) such that the quotient above is not a multiple of m or m itself, but a multiple of a smaller factor of m . Therefore when n is composite, there are at the very least 2 coefficients c k that are not multiples of n in the expansion.
Therefore, when n ≥ 2 , every coefficient except those of the first and last terms in the expansion of ( 1 + x ) n is divisible by n if and only if n ∈ P .