# Elementary number theory problem: If $m$ is a prime number and $a,b$ two numbers less than $m$, then prove the following

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!

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

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}\ )$$

• 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! – YourAverageEuler Oct 10 '17 at 18:19
• What about Fermat's theorem? – AnotherJohnDoe Oct 10 '17 at 18:24
• If someone do not know about modular arithmetic then asking him about Fermat little theorem doesn't make sense. :-P – I am Back Oct 10 '17 at 18:28
• I guess you're right! – AnotherJohnDoe Oct 10 '17 at 18:30

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}.$$

• @YourAverageEuler I edited my answer according to the modified statement. – Robert Z Oct 10 '17 at 18:19

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 .

• defo it is cuz the denominator will be 0. But I still don't understand... – YourAverageEuler Oct 10 '17 at 18:11
• No, that's not right@YourAverageEuler. You can only divide $if$ $a\neq b$ – AnotherJohnDoe Oct 10 '17 at 18:13
• The reason for $a\neq b$ follows simply from that the required result doesn't hold true for $a=b$ – AnotherJohnDoe Oct 10 '17 at 18:14
• @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$. – I am Back Oct 10 '17 at 18:14
• You're right; that's how I noticed it:) – AnotherJohnDoe Oct 10 '17 at 18:15