Assume that $p$ is a prime, $a$ and $b$ are integers such that $p \mid b$ and $am+b=1$.

78 Views Asked by At

Assume that $p$ is a prime, $a$ and $b$ are integers such that $p \mid b$ and $am+b=1$. Prove that $x \equiv m(1+b+b^2+...+b^{k-1} \bmod {p^k}$ is the solution to $ax\equiv 1 \bmod{p^k}$.

So I got that if $am+b \equiv 1$ then $am \equiv 1 \bmod{p}$ which means that $m\equiv a^{-1} \bmod p$. But thats all I got. Halp

2

There are 2 best solutions below

0
On

Observe that $am=1-b$, hence $$xam\ =\ x(1-b)\ =\ x-xb\ \equiv \ m \pmod{p^k}\,.$$ As $b$ is divisible by $p$, neither $a$ nor $m$ can be, so that $m$ is coprime to $p^k$, so we can divide by it mod $p^k$.

0
On

Since $am+b=1$ and $p\mid b$ we have $p\not\mid a$. Therefore the congruence $ax\equiv1\pmod{p^k}$ has a unique solution. So if we can show that the given expression is a solution, then it is the complete solution and we are finished. But if $x$ is the given expression then $$ax(1-b)\equiv am(1+b+\cdots+b^{k-1})(1-b)=am(1-b^k)\equiv am=1-b\ ,$$ and since $1-b$ is not a multiple of $p$ we can cancel it to get $$ax\equiv1\pmod{p^k}\ .$$