Proving Inverses in Z/mZ* for Non-Prime Numbers

[fishturtle1]

Homework Statement

In class yesterday we were learning about Z/mZ* where m is any nonnegative integer. At the very end(no time left), the teacher showed in Z/12Z* = {1, 5, 7, 11}, every element is its own inverse.

So $1*1 \equiv 1 \operatorname{(mod p)}$
$5*5 \equiv 1 \operatorname{(modp)}$.. etc.

So I want to prove: Let $x \epsilon \mathbb{Z}/m\mathbb{Z}^*$. Then $x = x^{-1}$, that is $x^2 \equiv 1 \operatorname{(mod p)}.$

Homework Equations

The Attempt at a Solution

Suppose $x \epsilon \mathbb{Z}/m\mathbb{Z}^*$. Then $\gcd(a, m) = 1$. So
$au + mv = 1$ for some integers u, v. We calculate $(au)^2 = (1 - mv)^2$ and get $a^2u^2 = m^2v^2 - 2mv + 1$... but there's no way to say $u = 1$ so i don't think this is the way..

I think I can prove this for prime numbers..Edit2: Never mind I think i just showed 1^2 = 1...
Edit1: Let $x \epsilon \mathbb{Z}/p\mathbb{Z}^*$ where p is prime. Then $\gcd(x,p) = 1$. So $x^{p-1} \equiv 1 \operatorname{(mod p)}$. Then $x^{p-1}x^{p-1} = x^{2(p-1)} = x^{{(p-1)}^2} \equiv 1^2 = 1 \operatorname{(modp)}$

 

[fresh_42]

Homework Statement

In class yesterday we were learning about Z/mZ* where m is any nonnegative integer. At the very end(no time left), the teacher showed in Z/12Z* = {1, 5, 7, 11}, every element is its own inverse.

So $1*1 \equiv 1 \operatorname{(mod p)}$
$5*5 \equiv 1 \operatorname{(modp)}$.. etc.

So I want to prove: Let $x \epsilon \mathbb{Z}/m\mathbb{Z}^*$. Then $x = x^{-1}$, that is $x^2 \equiv 1 \operatorname{(mod p)}.$

Homework Equations

The Attempt at a Solution

Suppose $x \epsilon \mathbb{Z}/m\mathbb{Z}^*$. Then $\gcd(a, m) = 1$. So
$au + mv = 1$ for some integers u, v. We calculate $(au)^2 = (1 - mv)^2$ and get $a^2u^2 = m^2v^2 - 2mv + 1$... but there's no way to say $u = 1$ so i don't think this is the way..

I think I can prove this for prime numbers..Edit2: Never mind I think i just showed 1^2 = 1...
Edit1: Let $x \epsilon \mathbb{Z}/p\mathbb{Z}^*$ where p is prime. Then $\gcd(x,p) = 1$. So $x^{p-1} \equiv 1 \operatorname{(mod p)}$. Then $x^{p-1}x^{p-1} = x^{2(p-1)} = x^{{(p-1)}^2} \equiv 1^2 = 1 \operatorname{(modp)}$

What is $3^{-1} \in \mathbb{Z}_7\,$?

 

[fishturtle1]

What is $3^{-1} \in \mathbb{Z}_7\,$?

5. So this doesn't hold for any m.. so maybe this holds only for composite m's? but that doesn't work because
$2*2 \equiv 4 \not\equiv 1 \operatorname{(mod 9)}$..
so then maybe it holds for only even composites? no that doesn't work since
$3*3 \equiv 9 \not\equiv 1 \operatorname{(mod 10)}$..

so was this just a coincidence?

 

[fishturtle1]

5. So this doesn't hold for any m.. so maybe this holds only for composite m's? but that doesn't work because
$2*2 \equiv 4 \not\equiv 1 \operatorname{(mod 9)}$..
so then maybe it holds for only even composites? no that doesn't work since
$3*3 \equiv 9 \not\equiv 1 \operatorname{(mod 10)}$..

so was this just a coincidence?

We know $(m-1)^2 = m^2 - 2m + 1 = m(m - 2) + 1$ so (m-1)^2 \equiv 1 (mod m). It seems in general, we can rewrite any $x \epsilon \mathbb{Z}_m$ as $x = m - r$ ,where $0 < r \le m-1$. So $x^2 = (m-r)^2 = m^2 -2mr + r^2 = m(m - 2r) + r^2$. So, $x^2 \equiv r^2 (\mod m)$. ... so yeah this seems like a coincidence...

 

[fresh_42]

so was this just a coincidence?

To be honest, I can't remember. I would start to read here:
https://en.wikipedia.org/wiki/Quadratic_reciprocity
https://en.wikipedia.org/wiki/Legendre_symbol
https://en.wikipedia.org/wiki/Jacobi_symbol
which might already contain the answer, but at least gives you the proper tools at hand.
My guess is that it depends on what $m \,(4)$ is, (edit) or $\varphi(m) (4)$.

 

[fishturtle1]

To be honest, I can't remember. I would start to read here:
https://en.wikipedia.org/wiki/Quadratic_reciprocity
https://en.wikipedia.org/wiki/Legendre_symbol
https://en.wikipedia.org/wiki/Jacobi_symbol
which might already contain the answer, but at least gives you the proper tools at hand.
My guess is that it depends on what $m \,(4)$ is.

Thank you for the links, ill check them out

 

[Dick]

so yeah this seems like a coincidence...

Largely coincidence, I think. You have a group with four elements and there are only two possibilities. It's either the Klein 4-Group (like this one and Z/8Z*) or it's cyclic (like Z/5Z* and Z/10Z*).