Prove that $\{x \mid(1+n)^{x}\equiv1+nx \pmod{n^2}\}=\{x \mid x^n\equiv 1\pmod{n^2}\}$

142 Views Asked by At

We have $n=pq$, with $p,q$ two different odd prime numbers.

I must prove that :

$A=\{x\in \mathbb{Z}/n\mathbb{Z} \mid (1+n)^{x}\equiv1+nx \pmod{n^2}\}=\{x\in (\mathbb{Z}/n^2\mathbb{Z})^{\times} \mid x^n\equiv 1\pmod{n^2}\}=B$.

Notice that $(1+n)^x \equiv 1+nx \pmod {n^2}$ and #$B=n=pq=$#$A$.

Maybe if I prove one inclusion and with equality of cardinality it will be fine.

Thanks in advance !

1

There are 1 best solutions below

1
On

The original problem was not clear enough as stated. Here is one attempt at proof. The ring of integers $\mathbb{Z}/n^2\mathbb{Z}$ has a multiplicative subgroup of elements $\{1+nx \mid x\in \mathbb{Z}/n\mathbb{Z}\}$. Because it is cyclic with generator $1+n$ and of order $n$, this is the same as $B$. The multiplication on the subgroup is $(1+nx)(1+ny)=1+n(x+y)$ and $(1+n)^x=1+nx$ expresses each element using the generator $(1+n)$. Thus, the additive group $A=\mathbb{Z}/n\mathbb{Z}$ is isomorphic to the multiplicative subgroup $B$. Thus $\#B=\#A$. The reason why this works is that $n$ is the product of distinct odd primes.