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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .