2
$\begingroup$

Problem:

If $m$ is a prime number and $a,b$ two distinct positive integers less than $m$ then prove that$$a^{m-2}+a^{m-3}b+a^{m-4}b^2+\cdots +b^{m-2}$$is a multiple of $m$

Source:

Found it on a mock test paper. I have just started learning number theory (thanks fleablood) for an exam, and I'm learning all of it on my own. The problem looks like a simple one but I can't seem to solve it.

My try:

The given expression looks very similar to binomial expansion of $(a+b)^{m-2}$ $$(a+b)^{m-2} = {{m-2}\choose{0}}a^{m-2}+{{m-2}\choose{1}}a^{m-3}b+\cdots+{{m-2}\choose{m-2}}b^{m-2}$$or $$(a+b)^{m-2} = a^{m-2}+{{m-2}\choose{1}}a^{m-3}b+\cdots+b^{m-2}$$ Now I have read a theorem which states that

The coefficient of every term in the expansion of $(a+b)^{p}$, except the first and the last, is divisible by $p$ where $p$ is a prime number

Which means that all the middle terms (except first and last) of the binomial expansion are divisible by $m$. But what about the first and last terms? And also the function given in problem is not a binomial expansion. How do I proceed? All help appreciated!

$\endgroup$
11
  • $\begingroup$ $(x^n - y^n) = (x - y)(x^{n - 1) + ... + y^{n - 1}).$ Also try using fermat's little. $\endgroup$
    – green frog
    Oct 10, 2017 at 17:53
  • $\begingroup$ I'm sorry I'm new to number theory, so any references please @ntntnt ? $\endgroup$ Oct 10, 2017 at 17:56
  • $\begingroup$ Wait do you want me to explain fermat's little or link you something that explains it? $\endgroup$
    – green frog
    Oct 10, 2017 at 18:00
  • 2
    $\begingroup$ It is false for $a=b$. Take $m=5$ and $a=b=2$. $\endgroup$
    – Robert Z
    Oct 10, 2017 at 18:00
  • $\begingroup$ Or $a=b=1, n=3$ $\endgroup$
    – user418131
    Oct 10, 2017 at 18:01

3 Answers 3

3
$\begingroup$

If $a\not=b$ then $$a^{m-2}+a^{m-3}b+a^{m-4}b^2+\cdots +b^{m-2}=\frac{(a^{m-1}-1)-(b^{m-1}-1)}{a-b}.$$ which is divisible by the prime $m$ because, by the Fermat's little theorem, $m$ divide $(a^{m-1}-1)$ and $(b^{m-1}-1)$ while $0<|a-b|<m$.

P.S. The property is false for $a=b$ because the prime $m$ does not divide $$a^{m-2}+a^{m-3}b+a^{m-4}b^2+\cdots +b^{m-2}=(m-1)a^{m-2}.$$

$\endgroup$
1
  • $\begingroup$ @YourAverageEuler I edited my answer according to the modified statement. $\endgroup$
    – Robert Z
    Oct 10, 2017 at 18:19
1
$\begingroup$

Note that the the condition only holds for $a\neq b$

We have $$a^{m-1}-b^{m-1}=(a-b)(a^{m-2}+a^{m-3}\ b+\ldots+b^{m-2}\ )$$

We also have, by Fermat's Little Theorem, that $$a^{p-1}\ \equiv 1\pmod p,$$ where $p$ is a prime, and $p\nmid a$.

It therefore follows that $$(a-b)(a^{m-2}+a^{m-3}\ b+\ldots+b^{m-2}\ )\ \equiv 0\pmod m$$$$\Rightarrow m\mid (a-b)\;\; OR\;\;m\mid (a^{m-2}+a^{m-3}\ b+\ldots+b^{m-2}\ )$$
The aboce follows from that $m$ is a prime.

Since we have $a,b\lt n$, and $a\neq b$, we conclude $m\nmid (a-b)$ $$\Rightarrow m\mid (a^{m-2}+a^{m-3}\ b+\ldots+b^{m-2}\ )$$

$\endgroup$
4
  • $\begingroup$ perfect! I'm not familiar with the mod function (will learn it very soon) and try to understand what you mean. Thanks for the effort and time! $\endgroup$ Oct 10, 2017 at 18:19
  • $\begingroup$ What about Fermat's theorem? $\endgroup$
    – user418131
    Oct 10, 2017 at 18:24
  • $\begingroup$ If someone do not know about modular arithmetic then asking him about Fermat little theorem doesn't make sense. :-P $\endgroup$ Oct 10, 2017 at 18:28
  • $\begingroup$ I guess you're right! $\endgroup$
    – user418131
    Oct 10, 2017 at 18:30
1
$\begingroup$

I let you conclude why it is wrong for $a=b$ from the theory below.

Note that you expression is equivalent to $\frac{a^{m-1}-b^{m-1}}{a-b}$.

Since $a,b$ are smaller than $m$, we only need to prove that $a^{m-1} -b^{m-1}$ is divisible by $m$. Which is true (using Fermat little theorem) since $a,b$ are smaller than $m$ and hence coprime to it as m is a prime .

$\endgroup$
6
  • $\begingroup$ defo it is cuz the denominator will be 0. But I still don't understand... $\endgroup$ Oct 10, 2017 at 18:11
  • $\begingroup$ No, that's not right@YourAverageEuler. You can only divide $if$ $a\neq b$ $\endgroup$
    – user418131
    Oct 10, 2017 at 18:13
  • $\begingroup$ The reason for $a\neq b$ follows simply from that the required result doesn't hold true for $a=b$ $\endgroup$
    – user418131
    Oct 10, 2017 at 18:14
  • 1
    $\begingroup$ @YourAverageEuler Well a nicer reason is that if $a=b$ then the LHS of you expression equals $(m-1)a^{m-2}$ which is not divisible by $m$. $\endgroup$ Oct 10, 2017 at 18:14
  • $\begingroup$ You're right; that's how I noticed it:) $\endgroup$
    – user418131
    Oct 10, 2017 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.