Помощ за една задачка

[Гост]

Намерете примитивните корени по модул 17. Решете сравнението x^7 ≡ 5 (mod 17).
Това е задачата ако някой може да ми каже какво е решението ще ми бъде много полезно.

Благодаря предварително

[nevrodermit]

За примитивните корени по модул 17:

Дефиниция: [tex]g[/tex] е примитивен корен на [tex]n[/tex], ако [tex]\forall a: \gcd(a,n)=1 \exists k: g^k \equiv a \mod n[/tex]
1) тест за числото 1: нека [tex]a=2[/tex], тогава искаме [tex]\exists k: 1^k \equiv 2 \mod 17[/tex], което очевидно не е така
2) тест за числото 2: гледаме остатъците на степените на 2 по модул 17:
[tex]2^0\equiv 1, 2^1\equiv 2, 2^2\equiv 4, 2^3\equiv 8, 2^4\equiv -1, 2^5 \equiv -2, 2^6\equiv -4, 2^7 \equiv -8, 2^8 \equiv 1[/tex]
След това те се въртят циклично и значи са винаги в множеството [tex]\{1,2,4,8,9,13,15,16\}[/tex].
Сега нека [tex]a=7[/tex], тогава искаме [tex]\exists k: 2^k \equiv 7 \mod 17[/tex], което очевидно не е така.
3) тест за числото 3: гледаме остатъците на степените на 3 по модул 17:
[tex]3^0\equiv 1, 3^1\equiv 3, 3^2\equiv 9, 3^3\equiv 10, 3^4\equiv 13, 3^5\equiv 5, 3^6\equiv 15, 3^7\equiv 11, 3^8 \equiv -1[/tex]. Тъй като стигнахме до [tex]-1[/tex] ще получим множеството от остатъците на степените на [tex]3[/tex] за степени от [tex]0[/tex] до [tex]7[/tex], но със знак минус. Т.е. ще получим общо [tex]16[/tex] остатъка, всички различни помежду си, тъй като [tex]\forall k,l\in I_{15}\cup {0}, k\ne l: 3^k \equiv 3^l \mod 17 \Leftrightarrow 3^{k-l} \equiv 1 \mod 17, 1\le |k-l|\le 15[/tex], което не е така както видяхме при изброяването.

Лема: Броят на примитивните корени по модул [tex]p[/tex] е [tex]\varphi(p-1)[/tex].
Доказателство:
Първо да отбележим, че броят на примитивните корени на [tex]p[/tex] не са повече от [tex]\varphi(p)[/tex], когато разглеждаме корените модул [tex]p[/tex].
Нека [tex]a[/tex] е примитивен корен [tex]p[/tex]. Тогава степените [tex]a^1, a^1,...,a^{p-1}[/tex] е система пълна остатъци модул [tex]p[/tex]. Ако някое от тях е примитивен корен, да кажем [tex]a^m[/tex]. Нека [tex]\gcd(m, p-1)=d \Rightarrow (a^m)^{\frac{p-1}{d}}\equiv (a^{p-1})^{\frac{m}{d}} \equiv 1 \mod p[/tex]. Ако [tex]d\ne 1, p-1=dp_1\Rightarrow (a^m)^{p_1}\equiv 1 \mod p[/tex]. Тъй като [tex]a^m[/tex] е примитивен корен единствено за [tex]p_1=p-1[/tex] е вярно, че [tex](a^m)^{p_1}\equiv 1[/tex] и значи [tex]d=1[/tex]. Оттук следва, че примитивните корени са [tex]\varphi(p-1)[/tex].

Лемата ни показва как можем да намерим останалите примитивни корени на [tex]17[/tex]. Засега сме намерили, че [tex]3[/tex] е. Следователно другите примитивни корени са степените на [tex]3[/tex] с вид [tex]3^k[/tex], където [tex]\gcd(16,k)=1[/tex], а именно [tex]k\in \{3,5,7,9,11,13,15\}[/tex]. По модул [tex]17: 3^3 \equiv 10, 3^5\equiv 5, 3^7 \equiv 11, 3^9\equiv -3\equiv 14, 3^{11}\equiv 7, 3^{13}\equiv 12, 3^{15}\equiv 6[/tex].
Значи примитивните корени на [tex]17[/tex] са в множеството [tex]\{3, 5,6,10,11,12,14\}[/tex].

За уравнението:
[tex]x^7 \equiv 5 \mod 17[/tex]. Нека [tex]g[/tex] е примитивен корен на 17, тъй като [tex]\gcd(5,17)=1 \exists k: g^k \equiv 5 \mod 17[/tex] . Искаме [tex]k=7[/tex]. Проверяваме примитивен корен след примитивен корен.
- [tex]3^7 \equiv 11[/tex] значи не е решение
- [tex]5^7 \equiv 25^3.5\equiv 8^3.5\equiv 64.40\equiv 13.6\equiv 10[/tex] значи не е решение
- [tex]6^7 \equiv 36^3.6\equiv 2^3.6\equiv 2.24\equiv 2.7\equiv 14[/tex] значи не е решение
- [tex]10^7 \equiv (-7)^7\equiv 49^3.(-7)\equiv (-2)^3(-7)\equiv 56\equiv 5[/tex] значи е решение
- [tex]11^7\equiv 121^3.11\equiv 2^3.11\equiv 4.22\equiv 4.5\equiv 20\equiv 3[/tex] значи не е решение
- [tex]12^7\equiv (-5)^7 \equiv -10\equiv -7[/tex] значи не е решение
- [tex]14^7\equiv (-3)^7\equiv -11\equiv -6[/tex] значи не е решение