2
$\begingroup$

Show that for $k \gt 0$ and $m \ge 1$, $x \equiv 1 \pmod {m^k}$ implies $x^m \equiv 1 \pmod {m^{k+1}}$

This question has already been asked in SE (Show that for $k \gt 0$ and $m \ge 1$, $x \equiv 1 \pmod {m^k}$ implies $x^m \equiv 1 \pmod {m^{k+1}}$.), but I think it´s not really answered. ( the hint given was enough but I didn’t realize it before)

I tried with Fermat´s little theorem but I get nowhere.

note: If $a \equiv b \pmod m$, then $a \cdot t \equiv b \cdot t \pmod {m \cdot t}$ with $t \gt 0$ (don´t know if this is useful)

Any help would be appreciated. Thanks.

$\endgroup$
4
  • 1
    $\begingroup$ That is correctly answered (though that was just a hint). You need to look closer to the binomial expansion. For the terms $r \geq 2$ they are divisible by $m^{k+1}$, and for the term $r = 0$ it is $1$, so you really need to look at only one term... $\endgroup$
    – Hw Chu
    Jul 24, 2019 at 22:36
  • $\begingroup$ What about the answer given to the linked question confuses you? $\endgroup$
    – rogerl
    Jul 24, 2019 at 22:37
  • $\begingroup$ @HwChu that is exactly what I don´t understand about it, because as I see it, when $r=1$ the term does not contain an $m^{k+1}$ then $x^m = 1 + nm^k + qm^{k+1}$ which is not what is desired, right? $\endgroup$ Jul 24, 2019 at 22:47
  • $\begingroup$ @Hw Chu now I see what you meant, thank you $\endgroup$ Jul 25, 2019 at 1:00

3 Answers 3

3
$\begingroup$

$x \equiv 1 \pmod {m^k}\implies$

There is an integer $M$ so that $x = 1 + Mm^k$.

$x = (1 + M*m^k)$ and $x^m = (1+M*m^k)^m$ and by binomial theorem will equal $1 + Mm^{k+1} + $ bunch of terms all times $m$ to power greater than $k+1$.

i.e.

So $x^m = (1 + Mm^k)^m = 1 + m*M*m^k + \sum_{j=2}^m {m\choose j}M^jm^{jk}=$

$1 + M*m^{k+1} + m^{k+1}\sum+{j=2}^m {m\choose j}M^jm^{jk-(k+1)}$.

(Note: If $j \ge 2$ then $jk-(k+1)=(j-1)k - 1\ge k-1 \ge 0$ so )

$Mm^{k+1} \equiv 0 \pmod{m^{k+1}}$ and $m^{k+1}\sum+{j=2}^m {m\choose j}M^jm^{jk-(k+1)}\equiv 0 \pmod{m^{k+1}}$

$x^m \equiv 1\pmod {m^{k+1}}$.

$\endgroup$
0
3
$\begingroup$

We have $x^m - 1 = (x-1) (x^{m-1} + x^{m-2} + \cdots + 1)$. Now, by hypothesis, $m^k \mid x-1$. On the other hand, since $k > 0$, we also have $x \equiv 1 \pmod{m}$, so $x^{m-1} \equiv 1 \pmod{m}$, $x^{m-2} \equiv 1 \pmod{m}$, ..., $1 \equiv 1 \pmod{m}$. Therefore, $x^{m-1} + x^{m-2} + \cdots + 1 \equiv 1 + 1 + \cdots + 1 = m \equiv 0 \pmod{m}$, so $m \mid x^{m-1} + x^{m-2} + \cdots + 1$.

$\endgroup$
2
$\begingroup$

Consequence of binomial expansion. If $$x=m^kn+1$$ then $$x^m=(m^kn+1)^m$$ the expansion of this has the exponent on $m$ in each term, except the last 2, greater than k( in fact multiples of k prior to coefficients). The last term is $1^m$ and the second last has ${{m}\choose {m-1}}=m$ as a coefficient. fleabloods answer tipped me off to my mistakes.

$\endgroup$

You must log in to answer this question.

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