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.


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.