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 '19 at 22:36
  • $\begingroup$ What about the answer given to the linked question confuses you? $\endgroup$ – rogerl Jul 24 '19 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$ – Octavio Berlanga Jul 24 '19 at 22:47
  • $\begingroup$ @Hw Chu now I see what you meant, thank you $\endgroup$ – Octavio Berlanga Jul 25 '19 at 1:00
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$

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.