Show that set of reduced residue classes is a subgroup of the multiplicative group of reduced residue classes

149 Views Asked by At

Let m $\in Z^+$ and let G denote the set of those residue classes a(mod m) such that $a^\frac{m-1}{2} = \left(\frac{a}{m}\right)$ (mod m). Show that if a $\in$ G and b $\in$ G then ab $\in$ G. Also show that if a $\in$ G and ac = 1 (mod m) then c $\in$ G.

For the first part, I use the multiplicative property of the jacobi: $(ab)^\frac{m-1}{2} = \left(\frac{a}{m}\right) \left(\frac{b}{m}\right)$ mod m = $\left(\frac{ab}{m}\right)$ (mod m).

For the second part, I start off again with $a^\frac{m-1}{2} = \left(\frac{a}{m}\right)$ (mod m) but I do not know how to bring c = $a^{-1}$ (mod m) into the equation. I tried breaking the jacobi down to prime factors in the denominator using $\left(\frac{P}{Q}\right) = \prod_{i=1}^{s} \left(\frac{P}{q_{j}}\right)$ and then using $a^\frac{p-1}{2} = \left(\frac{a}{p}\right)$ (mod p) for odd prime p, but this doesn't seem to get me anywhere.

1

There are 1 best solutions below

0
On

A number $a$ is residue $\mod m$ if there is $x$ such that $x^2 = a \mod m$.

1) Assume $a,b$ are residue $\mod m$, prove that $a b$ is residue $\mod m$.

Since $a,b$ are residue $\mod m$, then there is $x,y$ such that $x^2=a \mod m$ and $y^2 = b \mod m$, multiplying the two equations together gives $(x y)^2 = ab \mod m$ which means that there is $z$ such that $z^2 = ab \mod m$ namely $xy$, thus $ab$ is also residue $\mod m$.

2) Assume $a$ is residue $\mod m$ and $a c = 1 \mod m$, prove that $c$ is residue $\mod m$, there is $x$ such that $x^2 = a \mod m$ which means that $x^2 c=1 \mod m$, which means that $c = (\frac{1}{x})^2 \mod m$, which can be written as $ (x^{-1})^2 = c \mod m$, and thus $c$ is residue $\mod m$ ,because there will be inverse modulo for $x$. because if $x$ have no inverse modulo then $(x,m) \not= 1$ which lead to $(a,m) \not= 1$ which indicate that there is no inverse modulo for $a$ which contradict the assumption that $ac = 1 \mod m$

This conclude the proof.