2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Теория чисел, a^{20} = 1 (mod 100)
Сообщение24.05.2009, 20:47 
Аватара пользователя
Можно как-то доказать, что если $(100,a)=1$, то $a^{20} \equiv 1 \mod 100$ ?

$\phi(100)=40$, этого недостаточно для доказательства.

 
 
 
 Re: Теория чисел
Сообщение24.05.2009, 20:54 
Аватара пользователя
Перебором точно можно.
Код:
Prelude> map (\x -> x^20 `mod` 100) $ filter (\x -> gcd x 100 == 1) $ [0..99]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

 
 
 
 Re: Теория чисел
Сообщение24.05.2009, 20:57 
Аватара пользователя
Ну так я перебором это и обнаружил, мне интересно, есть ли другой способ :)

 
 
 
 Re: Теория чисел
Сообщение24.05.2009, 21:10 
Аватара пользователя
Если я нигде не напутал, можно так:
$a\equiv a_1\ (\mathrm{mod} 4)$
$a\equiv a_2\ (\mathrm{mod} 25)$
$a_1^{20}\equiv 1\ (\mathrm{mod} 4)$
$a_2^{20}\equiv 1\ (\mathrm{mod} 25)$ ($\varphi(25) = 20$)
и китайская теорема.

 
 
 
 Re: Теория чисел
Сообщение26.05.2009, 08:11 
Аватара пользователя
см. http://en.wikipedia.org/wiki/Carmichael_function

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group