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

  • Thread starter Thread starter fishturtle1
  • Start date Start date
Click For Summary

Homework Help Overview

The discussion revolves around the properties of the group Z/mZ* for non-prime integers, specifically examining whether each element is its own inverse. The original poster references a classroom example with Z/12Z* and seeks to prove that for any element x in Z/mZ*, x equals its inverse, leading to the equation x^2 ≡ 1 (mod m).

Discussion Character

  • Exploratory, Assumption checking, Conceptual clarification

Approaches and Questions Raised

  • Participants explore the implications of the original poster's claim, questioning whether the property holds for composite numbers and discussing specific cases where it does not seem to apply. There are attempts to derive generalizations based on examples and counterexamples, including considerations of even composites and specific modular arithmetic properties.

Discussion Status

The discussion is ongoing, with participants sharing insights and questioning the validity of the original claim. Some suggest that the observed behavior may be coincidental, while others propose that the outcome could depend on the specific structure of m. References to external resources have been made for further exploration.

Contextual Notes

Participants note that the behavior of inverses may vary based on the properties of m, particularly in relation to its prime factorization and the Euler's totient function φ(m). There is also mention of specific modular arithmetic examples that challenge the initial hypothesis.

fishturtle1
Messages
393
Reaction score
82

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)}##
 
Last edited:
Physics news on Phys.org
fishturtle1 said:

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\,##?
 
fresh_42 said:
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 said:
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...
 
Last edited:
fishturtle1 said:
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*).
 
  • Like
Likes   Reactions: fishturtle1

Similar threads

  • · Replies 4 ·
Replies
4
Views
1K
Replies
15
Views
4K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 11 ·
Replies
11
Views
2K
Replies
5
Views
2K
  • · Replies 16 ·
Replies
16
Views
2K
Replies
6
Views
4K
Replies
30
Views
3K
  • · Replies 13 ·
Replies
13
Views
4K
  • · Replies 5 ·
Replies
5
Views
2K