I came up with this proof for my number theory class. Is it valid?

Proposition: $u\in U_m \Rightarrow u^{\varphi(m)}=1$ (Where $U_m$ is the multiplicative group of integers modulo $m$)

Attempted Proof:

Lemma:$\forall a,b\in U_m$, $(a\cdot b)\in U_m$

Consider two numbers $a,b\in U_{m}$. Being in $U_m$, we know that they are coprime to $m$; in other words: $\exists p,q\in\mathbb{Z}: (mp+1=a)\land(mq+1=b)$.

$(a\cdot b)=(mp+1)(mq+1) \tag{Substitution Equality}$

$(mp+1)(mq+1)={m}^{2}pq+mp+mq+1 \tag{Simplifying}$

${m}^{2}pq+mp+mq+1=m(mpq+p+q)+1 \tag{Simplifying}$

$(mpq+p+q)\in\mathbb{Z} \tag{Closure}$

$\therefore [m(mpq+p+q)+1]\in U_m \tag{By definition of $U_m$}$

$\therefore (a\cdot b)\in U_m \tag{Substitution Equality}$ $$\Box$$

I know my teacher will be fine with everything up to this point. What comes next is where I would really like input.

Actual Proof:

$u\in U_m \tag{Given}$

$|U_m|=\varphi(m) \tag{Proven Before}$

We can, therefore write $U_m$ as the set $\{{c}_{1},{c}_{2},\ldots,{c}_{\varphi(m)}\}$, where $c$ is just a placeholder variable.

$$A:=\{x|(d\in {U}_{m})\land(x=u\cdot d)\}$$

To clarify, $A$ is simply a set of every element of $U_m$ multiplied by $u$ (i.e. $A=\{uc_{1},uc_{2},\ldots,uc_{\varphi(m)}\}$).

$\forall n\in A, n\in U_{m} \tag{Lemma}$

$|A|=|U_m| \tag{By Definition}$

Based upon these last two statements, we can assert that $A$ is a permutation of $U_m$. Consequently:

$$\prod^{\varphi(m)}_{x\in U_m}x \pmod m \equiv \prod^{\varphi(m)}_{x\in A}x \pmod m\tag{Commutativity}$$

$$\prod^{\varphi(m)}_{x\in U_m}x \pmod m \equiv \prod^{\varphi(m)}_{x\in U_m}(u\cdot x) \pmod m \tag{Substitution Equality}$$

$$\prod^{\varphi(m)}_{x\in U_m}x \pmod m \equiv {u}^{\varphi(m)}\prod^{\varphi(m)}_{x\in U_m} x \pmod m $$ $\tag{$\uparrow$Property of Multiplication}$

$$1\pmod m \equiv {u}^{\varphi(m)}\pmod m \tag{Cancelling}$$

$$\therefore {u}^{\varphi(m)} \pmod m \equiv 1 \tag{$1\bmod m \equiv 1$}$$ $$\blacksquare$$

Does this work? Thanks for reading!

  • 1
    $\begingroup$ It looks fine...but lengthy because it uses only very basic stuff. Nice.+1 $\endgroup$ – DonAntonio Nov 30 '13 at 16:12
  • $\begingroup$ @DonAntonio Yeah it's a high school independent study, so we haven't done things like group theory yet. Thanks for the feedback. $\endgroup$ – belph Nov 30 '13 at 17:40
  • 1
    $\begingroup$ Oh, dear! Kudos for the effot, @sudo. It's very nice for high school level. $\endgroup$ – DonAntonio Nov 30 '13 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.