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 Answers 2

Reset to default
3
$\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$
3
  • $\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
    Apr 29, 2016 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, 2016 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, 2016 at 20:50
3
$\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$
1
  • $\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
    Apr 29, 2016 at 20:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .