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$
  • $\begingroup$ $(x^n - y^n) = (x - y)(x^{n - 1) + ... + y^{n - 1}).$ Also try using fermat's little. $\endgroup$ – 伽罗瓦 Oct 10 '17 at 17:53
  • $\begingroup$ I'm sorry I'm new to number theory, so any references please @ntntnt ? $\endgroup$ – YourAverageEuler Oct 10 '17 at 17:56
  • $\begingroup$ Wait do you want me to explain fermat's little or link you something that explains it? $\endgroup$ – 伽罗瓦 Oct 10 '17 at 18:00
  • 2
    $\begingroup$ It is false for $a=b$. Take $m=5$ and $a=b=2$. $\endgroup$ – Robert Z Oct 10 '17 at 18:00
  • $\begingroup$ Or $a=b=1, n=3$ $\endgroup$ – AnotherJohnDoe Oct 10 '17 at 18:01
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$
  • $\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$ – YourAverageEuler Oct 10 '17 at 18:19
  • $\begingroup$ What about Fermat's theorem? $\endgroup$ – AnotherJohnDoe Oct 10 '17 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$ – I am Back Oct 10 '17 at 18:28
  • $\begingroup$ I guess you're right! $\endgroup$ – AnotherJohnDoe Oct 10 '17 at 18:30
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$
  • $\begingroup$ @YourAverageEuler I edited my answer according to the modified statement. $\endgroup$ – Robert Z Oct 10 '17 at 18:19
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$
  • $\begingroup$ defo it is cuz the denominator will be 0. But I still don't understand... $\endgroup$ – YourAverageEuler Oct 10 '17 at 18:11
  • $\begingroup$ No, that's not right@YourAverageEuler. You can only divide $if$ $a\neq b$ $\endgroup$ – AnotherJohnDoe Oct 10 '17 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$ – AnotherJohnDoe Oct 10 '17 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$ – I am Back Oct 10 '17 at 18:14
  • $\begingroup$ You're right; that's how I noticed it:) $\endgroup$ – AnotherJohnDoe Oct 10 '17 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.