# Inverse number and linear congruence

Find all integer between 1 to 30 that have inverse modulo 30 and for each one find its inverse.

Well, I think there are 8 number that have inverse modulo 30: $1,7,11,13,17,19,23,29$.

I guess the inverse of 1 is 1.

BUT how to I find the inverse of all other number?

-

Note that if $b=a^{-1}$, then $a=b^{-1}$, so the inverse of each number in that list is also in the list, so trial and error is quite feasible in this case. We can improve a bit on pure trial and error, though, even without using any special techniques to solve congruences.

As you say, $1$ is its own inverse. $29\equiv-1\pmod{30}$, so $29^2\equiv(-1)^2\equiv1\pmod{30}$, and $29$ is also its own inverse. Now $7\cdot13=91\equiv1\pmod{30}$, so $7$ and $13$ are multiplicative inverses of each other. And since $23\equiv-7\pmod{30}$ and $17\equiv-13\pmod{30}$, we must have

$$23\cdot17\equiv(-7)(-13)\equiv7\cdot13\equiv1\pmod{30}\;,$$

so $23$ and $17$ are inverses of each other. That leaves only $11$ and $19$. $11^2=121\equiv1\pmod{30}$, so $11$ is its own inverse, and therefore $19\equiv-11\pmod{30}$ must also be its own inverse, just as with $29$ above. (Or you can simply note that $19^2=361\equiv1\pmod{30}$.

$19\equiv-11\pmod{30}$,

-

The numbers that have inverses are those that are coprime with $30$.

Since $\phi(30)=8$. Thus by Euler's theorem, the inverse of $x$ is $x^7$

-
Don't know what Euler theorem is so I guess im not supposed to use it. –  Mary Dec 7 '12 at 21:13
Hmm. In this case you can use trial and error. Let me think about a smarter way. –  Amr Dec 7 '12 at 21:14
Solve the congruence relationships $1\cdot x_1\equiv1\pmod{30}$, $7\cdot x_7\equiv 1\pmod{30}$, etc, so that $x_{p}$ is the inverse for $p$ modulo 30.