-1

Find the multiplicative inverse of $n+1$ modulo $n^2$ , where $n$ is any integer greater than $1$

We have to find $z$ such that $(n+1)z=1\pmod{n^2}$ $$ n^2-k(n+1)=n^2-kn-k=1\implies n^2-kn-(k+1)=0\\ \implies n=k+1\text{ or }-1\implies \boxed{k=n-1}\\ n^2-(n-1)(n+1)=1 $$ For $a>b$ using Euclid's algorithm we can conclude that $\gcd(a,b)=\gcd(a-b,b)$. $$ \gcd(n^2,n+1)=\gcd(n^2-(n+1),n+1)=\gcd(n^2-2(n+1),n+1)=\cdots=\gcd(n^2-(n-1)(n+1),n+1)=\gcd(1,n+1)=1 $$ $\implies $ inverse exists

But how do I proceed further? Can we follow the same steps for a particular integer ?

For example if it were to find $27$ modulo $4$ then

$27b=1\pmod4$ and $\gcd(27,4=1)\implies $ inverse exists

$$ 27=6\times 4+3\\ 4=1\times 3+3 $$ $$ 3=27-6\times 4\\ 1=4-1\times 3 $$ $$ 1-4-1\times 3=4-1(27-6\times 4)=4-1\times 27+6\times 4\\ 1=7\times 4-1\times 27\\ 27\times -1=-7\times 4+1\\ 27\times -1=1\pmod 4 $$

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
Sooraj S
  • 7,357
  • 3
  • 40
  • 78
  • Divide $n^2=(n+1)(n-1)+1$. Therefore $(n+1)(-n+1)=n^2(-1)+1$. In general, you do Euclid's algorithm to produce [Bezout's equation](https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#B%C3%A9zout's_identity_and_extended_GCD_algorithm). This gives you polynomials $a,b$ such that $a(n)n^2+b(n)(n+1)=1$. Then the inverse of $n+1$ modulo $n^2$ is $b(n)$. – plop Dec 05 '21 at 13:19
  • The inverse is $1-n$. – Crostul Dec 05 '21 at 13:19
  • As explained [here](https://math.stackexchange.com/a/3224776/242) in the 1st linked dupe (see "nilpotents") $\ $ $$\bmod \color{#c00}{n^2}\!:\,\ \dfrac{1}{1+n} = \dfrac{1-n}{1-\color{#c00}{n^2}\!} = \dfrac{1-n}{1-\color{#c00}0}\qquad\qquad$$ See [here](https://math.stackexchange.com/a/3225783/242) in the 2nd dupe for another example of inverting a **unit + nilpotent**. – Bill Dubuque Dec 05 '21 at 14:16
  • @BillDubuque Is the recursive substitution method I used a special case of those results? – CyclotomicField Dec 05 '21 at 14:24
  • **Or** use Hensel's Lemma: $\bmod n\!:\ 1 \equiv (n\!+\!1)x\equiv x\iff x = 1\! +\! kn,\,$ so $\bmod n^2\!:\ 1 \equiv (1\!+\!n)x\equiv (1\!+\!n)(1\!+\!kn) \equiv 1 + n(1\!+\!k) \iff k\equiv -1\pmod{n}$ $\iff x\equiv 1-n\pmod{n^2}\ \ $ – Bill Dubuque Dec 05 '21 at 14:27
  • **Or** use a couple steps of the [extended Euclidean algorithm](https://math.stackexchange.com/a/2959891/242) to get the Bezout identity for $\,\gcd(n^2,1+n)=1,\,$ viz. $\, n^2 + (1-n)(1+n) = 1\ \ $ – Bill Dubuque Dec 05 '21 at 14:36
  • It's not clear what you mean by the "recursive subst, method". Please elaborate. – Bill Dubuque Dec 05 '21 at 14:37

2 Answers2

1

Since $(n+1)(n-1) \equiv (-1) \pmod{n^2}$ and since $(-1)^2 \equiv 1\pmod{n^2}$, you have that

$[(n+1)(n-1)]^2 \equiv 1\pmod{n^2}.$

Therefore, the inverse of $(n+1)$ is $[(n+1)(n-1)^2]$.

This inverse simplifies to $(-1)(n-1) = (1 - n)$.

user2661923
  • 32,142
  • 3
  • 15
  • 36
0

Given $(n+1)z=1 \mod n^2$ we see that $$z=1-zn=1-(1-zn)n=1-n-zn^2=1-n\mod n^2$$

CyclotomicField
  • 9,183
  • 1
  • 10
  • 26