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

[Mr.G{}{}Fy]

Да се докаже,че примитивни корени по модул [tex]2^n[/tex] съществуват само при [tex]n=1[/tex] или [tex]n=2[/tex]

[nevrodermit]

Лема: Ако е нечетно, то [tex]a^{2^{n-2}}\equiv 1 \mod 2^n[/tex] за [tex]n\ge3[/tex].
Доказателство: индукция по [tex]n[/tex]:
1) За [tex]n=3[/tex] трябва да покажем, че [tex]a^2\equiv 1 \mod 8[/tex]. Тъй като [tex]1^2\equiv 3^2\equiv5^2\equiv7^2\equiv 1 \mod 8[/tex] е вярно.
2) Нека твърдението е вярно за някое [tex]n>1[/tex].
3) Искаме да докажем, че [tex]a^{2^{n-1}}\equiv 1 \mod 2^{n+1}[/tex].
Имаме [tex]a^{2^{n-2}}\equiv 1 \mod 2^n \Rightarrow a^{2^{n-2}}=2^nk+1[/tex]. Повдигаме на втора степен двете страни и получаваме [tex]a^{2^{n-1}}=(2^nk+1)^2=2^{2n}k^2+2^{n+1}k+1\equiv 1 \mod 2^{n+1}[/tex].
С това доказахме лемата.

Дефиниция: Примитивен корен [tex]a[/tex] на [tex]n[/tex] може да се дефинира като:
1) [tex]\gcd(a,n)=1[/tex]
2) най-малкото естествено число [tex]e[/tex], за което [tex]a^e\equiv 1 \mod n[/tex] е [tex]\varphi(n)[/tex]

След тази дефиниция, забелязваме, че [tex]\varphi(2^n)=2^{n-1}[/tex], докато в лемата сме открили по - малка степен, което е противоречие.
Следователно, няма примитивни корени за [tex]n\ge 3[/tex].

Остава да дадем примери за примитиви корени на [tex]2[/tex] и [tex]4[/tex].
- за 2, очевидно 1 му е примитивен корен, понеже [tex]\varphi(2)=1[/tex], [tex]\gcd(2,1)=1[/tex]
- за 4, нека пробваме с 3: [tex]3^1\equiv 3, 3^2\equiv 9\equiv 1, \varphi(4)=2[/tex], следователно му е примитивен корен