4
$\begingroup$

I'm currently studying Number Theory and I've stumbled upon a question where I need to: Find the sum of all products of pairs of distinct primitive roots mod 83.

Solving attempt: I've tried to find all the primitive roots mod 83 but then I realized that there are probably many of them and the calculations are getting heavy on high powers. I guess there might be a simpler approach then just finding all the primitive roots and summing all the products of distinct primitive roots. I do know that the product of all primitive roots (mod p) is 1 mod p but I don't see how it helps me.

Any help would be appreciated.

$\endgroup$
2
$\begingroup$

Let $g$ be a primitive root of $83$. Then all the primitive roots are $g^k$ where $k$ is relatively prime to $82$, so all $g^k$ with odd $k$ from $k=1$ to $k=81$, with the exception of $k=41$. These are all the quadratic non-residues of $83$ except $-1$.

Let $S$ be the sum of the primitive roots. Then the sum of the quadratic non-residues of $83$ is congruent to $S-1$ modulo $p$. This is $0$ modulo $83$, so $S\equiv 1\pmod{83}$.

The sum of the squares of the quadratic non-residues is congruent to $0$ modulo $83$. This is because $83$ is of the form $4k-1$, so $x$ is a QR if and only if $-x$ is an NR. So the sum $T$ of the squares of the primitive roots is congruent to $-1$.

Our sum of products is $\frac{1}{2}(S^2-T)$, which is congruent to $1$ modulo $p$.

$\endgroup$
  • $\begingroup$ Thank you for your answer, I have a few questions though: I don't understand why the sum of quadratic non-residues of 83 is S-1 mod 83 and how it gives me that $S\equiv 1\pmod{83}$. And in the third paragraph I can't understand how does it follow that sum of the squares of primitive roots is congruent to -1.. I'd appreciate if you could clarify those parts a little. $\endgroup$ – Evgeny A. Apr 29 '16 at 20:18
  • 1
    $\begingroup$ If the sum of the primitive roots is $S$, then since the only additional non-residue is $-1$ (aka $82$), the sum of the quadratic non-residues is congruent to $S-1$. But the sum of the quadratic non-residues is $0$ modulo $83$. Standard result for all primes $\gt 3$. Can prove it by looking at $1+2+\cdots +83$, divisible by $83$, minus the sum $1^2+2^2+\cdots +41^2$, also divisible by $83$. (More) $\endgroup$ – André Nicolas Apr 29 '16 at 20:42
  • 1
    $\begingroup$ (More) The squares of the NR give us the PR, in some order. I gave detail about why this sum is congruent to $0$. But the sum of the squares of the NR includes $(-1)^2$, which is the only one which is not the square of a primitive root. So the sum of the squares of the primitive roots is $\equiv -1\pmod{83}$. $\endgroup$ – André Nicolas Apr 29 '16 at 20:50
2
$\begingroup$

Given any polynomial $f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0\in\mathbb C[x]$ with complex roots $p_1,\dots,p_n$ (counted with multiplicity), we have $$ \sum_{i\neq j}p_ip_j=\frac{a_{n-2}}{a_n} $$ following from Vieta's formulas. Consider the cyclotomic polynomial $$\Phi_{83}(x)=\prod_{\zeta\text{ primitive $83^\text{th}$ root}}(x-\zeta).$$ Since $83$ is prime, there is a formula you can use to calculate $\Phi_{83}$. Can you finish it from here?

$\endgroup$
  • $\begingroup$ Thanks for the answer, unfortunately I'm not familiar yet with cyclotomic polynomials and I have to use the tools I've learned so I'll try to continue with Andre's answer. $\endgroup$ – Evgeny A. Apr 29 '16 at 20:22

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.