Let $n$ be a positive integer and $a$ be an integer such that $a$ is its own inverse modulo $n$. What is the remainder when $a^2$ is divided by $n$?

RektTheNoob
Aug 10, 2017

#1**+1 **

**Let n be a positive integer and a be an integer such that a is its own inverse modulo n. What is the remainder when a^2 is divided by n?**

A modular inverse of an integer a (modulo n) is the integer \(a^{(-1)}\) such that

\(aa^{(-1)}=1 \pmod n\)

So let \(a^{(-1)} = a\), we have:

\(\begin{array}{|rcll|} \hline a\cdot a &=& 1 \pmod n \\ a^2 &=& 1 \pmod n \\ \hline \end{array}\)

The remainder when a^{2} is divided by n ist **1**

heureka
Aug 11, 2017

#1**+1 **

Best Answer

**Let n be a positive integer and a be an integer such that a is its own inverse modulo n. What is the remainder when a^2 is divided by n?**

A modular inverse of an integer a (modulo n) is the integer \(a^{(-1)}\) such that

\(aa^{(-1)}=1 \pmod n\)

So let \(a^{(-1)} = a\), we have:

\(\begin{array}{|rcll|} \hline a\cdot a &=& 1 \pmod n \\ a^2 &=& 1 \pmod n \\ \hline \end{array}\)

The remainder when a^{2} is divided by n ist **1**

heureka
Aug 11, 2017