Powerful Primes #2

Number Theory Level 3

$\large (x-1)^{43} - (x^{43} - 1)$

When the expression above is expanded and simplified, how many of the coefficients are divisible by 43?

The answer is 42.

2 solutions

Raj Rajput
Aug 24, 2015

Moderator note:

As Pi Han Goh has pointed out, you need to show that all of its terms are divisible by 43.

You still need to show that $\dbinom{43}{1} , \dbinom{43}{2}, \dbinom{43}{3},\ldots , \dbinom{43}{42}$ are all divisible by 43.

Read this .

Pi Han Goh - 5 years, 9 months ago

Done @Pi Han Goh :)

RAJ RAJPUT - 5 years, 9 months ago

No. you have only shown that the first terms are divisible by 43. It may appears to be true for the first few terms but it might not be true for all the terms. You need to prove that $\dbinom{n}{k} \equiv 0 \pmod n$ for $n$ prime and $0 < k <n$ .

Pi Han Goh - 5 years, 9 months ago

@Pi Han Goh – how can i do this help needed, is there any approach for that ??

RAJ RAJPUT - 5 years, 9 months ago

@Raj Rajput – Hint: Fermat's Little Theorem.

Pi Han Goh - 5 years, 9 months ago

@Pi Han Goh – :( i don't know about that theorem .. is there any book for such theorems

RAJ RAJPUT - 5 years, 9 months ago

@Raj Rajput – Fermat's Little Theorem .

Pi Han Goh - 5 years, 9 months ago

Chew-Seong Cheong
Aug 25, 2015

$\begin{aligned} (x-1)^{43} - (x^{43}-1) & = x^{43} - \begin{pmatrix} 43 \\ 1 \end{pmatrix} x^{42} + \begin{pmatrix} 43 \\ 2 \end{pmatrix} x^{41} -... -1 - (x^{43}-1) \\ & = - \begin{pmatrix} 43 \\ 1 \end{pmatrix} x^{42} + \begin{pmatrix} 43 \\ 2 \end{pmatrix} x^{41} - \begin{pmatrix} 43 \\ 3 \end{pmatrix} x^{40} + ... + \begin{pmatrix} 43 \\ 42 \end{pmatrix} x \end{aligned}$

We note that all $\boxed{42}$ coefficients $\displaystyle \begin{pmatrix} 43 \\ k \end{pmatrix}$ for $k=1,2,3,...42$ are divisible by $43$ .

Moderator note:

This is not complete.

It might be true that $\dbinom{43}{1} ,\dbinom{43}{2} ,\dbinom{43}{3}$ are divisible by 43 but you need to show that $\dbinom{43}{k}$ is divisible by 43 for integer $0 < k < 43$ .

It is not always true that $\dbinom{n}{k}$ is divisible by positive integer $n$ for integer $0<k<n$ . Take $n=8$ as a counterexample.

Powerful Primes #2

The answer is 42.

2 solutions

Moderator note:

Moderator note:

0 pending reports