Всё решил. Кроме этой задачки https://academ.club/html/emoticons/rolleyes.gif Но она ДОЛЖНА быть лёгкой.

Задачка:

Пусть p = 2^(2^n) + 1 - простое число Ферма. Док-ть, что если n >= 1, то 3 - первообразноый корень по модулю p.

если мне не изменяет память, то эта задачка из синенького учебника (не помню автора) с тремя звёздочками. Если это так и преподаватель у тебя Викентьев, то в прошлом году даже он не мог объяснить как она решается, поэтому всем и даёт на зачёте и у меня тоже не получилось..

Удачи!

QUOTE (Mamontenok @ Dec 23 2006, 09:21)

если мне не изменяет память, то эта задачка из синенького учебника (не помню автора) с тремя звёздочками

синенький - это, вроде бы, блощицын.

 

еще бывает виноградов, но он красненький и не задачник https://academ.club/html/emoticons/wink.gif

QUOTE (MikeZ @ Dec 20 2006, 21:50)

Всё решил. Кроме этой задачки https://academ.club/html/emoticons/rolleyes.gif Но она ДОЛЖНА быть лёгкой.   Задачка:   Пусть p = 2^(2^n) + 1 - простое число Ферма. Док-ть, что если n >= 1, то 3 - первообразноый корень по модулю p.

Рассмотрим некоторый первообразный корень a по модулю p. Тогда

3=a^k (mod p).

1) Пусть k - чётное, тогда 3 - квадратичный вычет по модую p. Из закона взаимности квадратичных вычетов имеем (p/3)(3/p) = 1, где (p/3) и (3/p) символы Лежандра, т.е. 1=(p/3)= p^((3-1)/2)= p(mod 3). Тогда p-1 делится на 3. Противоречие.

2) Пусть k-нечётное. Пусть m таково, что 3^m=a^(km)(mod p). Тогда km=t(p-1). Тогда p-1 делит m. Следовательно 3 - первообразный корень по модулю p.