Примитивен корен

[asdf]

Нека P и q са прости числа, такива че P=2q+1. Да се докаже, че поне едно от числата 2 и -2 е примитивен корен по модул p

[nikko]

Ще използвам следната:
Теорема - Ако p и q са нечетни прости числа и [tex]p=2q+1[/tex], то множеството на примитивните корени по модул p съвпада с множеството от квадратичните неостатъци по модул p, с изключение на [tex]a=p-1(\text{mod}\ p)[/tex]
Доказателство: Нека S е множеството на примитивните корени по модул p и T да е подмножеството на [tex]\mathbb{Z}_p[/tex], състоящо се от квадратични неостатъци по модул p. Ако [tex]a\in S[/tex], то [tex](a, p) = 1[/tex] и [tex]a^{p-1}\equiv 1(\text{mod}\ p)[/tex]. Понеже p-1 е най-ниската степен на a, която е сравнима с 1, то [tex]a^{\frac{p-1}{2}}\equiv -1(\text{mod}\ p)[/tex] и следователно [tex]S\subseteq T.[/tex]
Освен това [tex]|S|=\varphi(\varphi(p))=\varphi(p-1)=\varphi(2q)=q-1[/tex].
Имаме [tex]|T|=\frac{p-1}{2}=q[/tex] и [tex]|T|-|S|=1[/tex]. Да разгледаме [tex]a=p-1\equiv -1(\text{mod}\ p)[/tex].
Понеже [tex]\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=(-1)^q=-1[/tex], то [tex]-1\in T[/tex], a [tex](-1)^2\equiv1(\text{mod}\ p)[/tex], т.е. [tex]-1\notin S[/tex].

В твоята задача ситуацията е подобна.
I. Ако q е четно, то q=2 и p=5,
[tex]2^0=1(\text{mod}\ 5)[/tex], [tex]2^1\equiv 2(\text{mod}\ 5)[/tex], [tex]2^2\equiv 4(\text{mod}\ 5)[/tex], [tex]2^3\equiv 3(\text{mod}\ 5)[/tex], т.е. 2 е примитивен корен по модул 5.
II. q е нечетно и [tex]p=2q+1\geq 7[/tex] очевидно също е нечетно. Понеже [tex]p>3[/tex], то 2 и -2 не са сравними с -1 по модул p и точно едно от тях е квадратичен остатък, а другото е неостатък, следователно според теоремата 2 или -2 е примитивен корен по модул p.

Защо едно от двете числа 2 и -2 е квадратичен остатък, а другото е неостатък. [tex]\left(\frac{2}{p}\right)\left(\frac{-2}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2^2}{p}\right)=\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=(-1)^q=-1[/tex]
Така отляво двата символа на Льожандър са с различни знаци.

[Станислав]

Доказателството, което nikko представи, е интересно. Ето и едно по-достъпно. Ако [tex]k_{1}[/tex] и [tex]k_{2}[/tex] са съответно показателите на [tex]2[/tex] и [tex]-2[/tex] по модул p. Ясно е, че те са измежду [tex]\{1,2,q,2q\}[/tex]. 1 и 2 не водят до решения, т.е [tex]k_{1}[/tex] и [tex]k_{2}[/tex] са сред [tex]\{q,2q\}[/tex] Ако допуснем, че нито 2, нито -2 не са примитивни корени ще следва, че [tex](\frac{2}{p})=(\frac{-2}{p})=1\Rightarrow (\frac{-1}{p})=1[/tex] съгласно мултипликативността на символа на Льожандър. Последното, обаче значи [tex]p\equiv 1 (mod 4)[/tex], откъдето [tex]q=2[/tex]. Непосредствената проверка на този случай показва, че 2 е примитивен корен по модул 5 - противоречие!

[Станислав]

Друга сходна задача е следната:
Простите [tex]p[/tex] и [tex]q[/tex] са свързани с равенството [tex]p=4q+1[/tex] . Докажете, че 2 е примитивен корен по модул [tex]p[/tex].

[asdf]

Благодаря за решенията. Май ще ми трябва малко повечко време, за дa осмисля това на nikko пълноценно, но много благодаря Сега ще пробвам задачата на станислав