Let $p$ a prime number and $d$ a divisor of $p-1$. Find the product of elements in $\mathbb Z_p$ with order $d$. ($\mod p$). (10 points)
Problem
Source: Iran 3rd round 2013 - Number Theory Exam - Problem 1
Tags: modular arithmetic, number theory, relatively prime, number theory proposed, Modular inverse, Multiplicative order
11.09.2013 20:01
Again, the lemma from one of the proofs of Wilson's theorem. The numbers from $2$ to $p-2$ can be arranged in pairs $(x,y)$, $x\ne y$ such that $xy \equiv 1 \pmod p$. For each $x$, we can find a unique such $y$. So, if $ord_p(x)=d$, then obviously $ord_p(y)=ord_p(\frac{1}{x})=d$, which means the product is $1$ modulo $p$ if $d\ne 2$, $-1$ otherwise.
13.09.2013 01:22
This problem is equivalent to computing $\Phi_d(0)$, which is equal to $1$ since all the roots of $\Phi_d$ come in conjugate pairs and are on the unit circle.
07.04.2014 08:28
Let $a$ be an integer having order $d$ modulo $p$.We know that if $d|p-1$ then the equation $x^d-1 \equiv 0\pmod{p}$ has exactly $d$ incongruent solutions ,these being $a,a^2,a^3,a^4,.....,a^d$.Hence all the incrongruent integers having order $d$ modulo $p$ belongs from this set.From a standard result we have $ord_p(a^h)=\frac{d}{gcd(h,d)}$ so we must have $gcd(h,d)=1$ We also know that $\sum_{k=1}^{\phi(d)}{b_k}=\frac{1}{2}d\phi(d)$ where $b_1,b_2,....,b_{\phi(d)}$ are the $\phi(d)$ integers less than $d$ and relatively prime to $d$.Thus required product $=a^{\frac{1}{2}d\phi(d)} \equiv 1\pmod{p}$.
26.08.2016 13:31
If $g$ is the primitive root of $p$ then we know that {$1,2,...,p-1$}={$g^0,g^1,...,g^{p-2}$} (mod $p$) and if $p-1=d.t$ then $ord_p(g^i)=\frac{p-1}{(p-1,i)}=d$ So $(p-1,i)=t$ so the required product is $g^t($the sum of numbers less than $d$ and coprime to $d$) and it is obviously equal to 1 mod $p$
22.07.2023 11:01
Let $x$ be some element in the set $\{2,3,\cdots,p-1\}.$ Since $p$ is prime and $1$ is its own inverse, there must exist some modulo inverse $y\in\{2,3,\cdots,p-1\}$, so that $xy\equiv1\pmod{p}.$ Then it follows that \begin{align*} y^{\text{ord}_p(x)}&\equiv(xy)^{\text{ord}_p(x)}(x^{\text{ord}_p(x)})^{-1}\\ &\equiv1^{\text{ord}_p(x)}1^{-1}\pmod{p}\\ &\equiv1\pmod{p}. \end{align*}Similarly, using the above, we obtain that \begin{align*} y^{\text{ord}_p(x)-1}&\equiv y^{\text{ord}_p(x)}y^{-1}\pmod{p}\\ &\equiv1\cdot y^{-1}\pmod{p}\\ &\equiv x\pmod{p}\\ &\not\equiv 1\pmod{p}, \end{align*}where the final step follows from our assumption that $y\in\{2,3,\cdots,p-1\}.$ From the above computations, it follows that $$\text{ord}_p(x)=\text{ord}_p(y).$$Since $\text{ord}_p(1)=\text{ord}_p(1)=1$, we see that the identity $\text{ord}_p(x)=\text{ord}_p(y)$ follows for all $x\in\{1,2,\cdots,p-1\}.$ In other words, order modulo $p$ is preserved across inverses for all elements in $\mathbb{Z}/p\mathbb{Z}^\times.$ If $x$ is its own inverse modulo $p$, so that $x^2\equiv1\pmod{p}$, we must have that $p\mid x^2-1=(x-1)(x+1)$, so that $p\mid x-1$ or $p\mid x+1$; in other words, $x$ is its own inverse iff $x\equiv\pm1\pmod{p}.$ Thus, we can pair up the $p-3$ elements of $\{2,3,\cdots,p-2\}$ into disjoint pairs $(x,y)$ such that $xy\equiv1\pmod{p}.$ For some $d\mid p-1$ with $d\ge3,$ the associated set $S$ consisting of exactly the $x\in\{1,2,\cdots,p-1\}$ such that $\text{ord}_p(x)=d$ must be a subset of $\{2,3,\cdots,p-2\}$, as $d\neq\text{ord}_p(1)=1$ or $d\neq\text{ord}_p(p-1)=2.$ Furthermore, $S$ must be closed under inverses, as order modulo $p$ is preserved across inverses, as shown previously. It follows that we can partition $S$ into various disjoint $S_i=\{x_i,y_i\}$ such that $x_iy_i\equiv1\pmod{p},$ so that \begin{align*} \prod_{x\in S}x&\equiv\prod_{i=1}^{\frac{|S|}2}x_iy_i\pmod{p}\\ &\equiv\prod_{i=1}^{\frac{|S|}2}1\pmod{p}\\ &\equiv1\pmod{p}. \end{align*} As noted before, we have $d\le2$ iff its associated $S$ is a subset of $\{1,p-1\}.$ Specifically, if $d=1$, then $S=\{1\}$, so that $\prod_{x\in S}x=1.$ If $d=2$, then $S=\{p-1\}$, giving $\prod_{x\in S}x=p-1.$ In conclusion, we have that $\prod_{x\in S}x$ is congruent to $-1\pmod{p}$ iff $d\neq2$ and to $1\pmod{p}$ otherwise. $\blacksquare$