308
правок
Изменения
м
→Теорема о НОД периодов
|proof=Обозначим <tex> r = \gcd(p, q) </tex>. Доказательство будем вести индукцией по <tex> n = (p + q) / r </tex>.
В случае <tex> p = q </tex> видим что <tex> n = 2 </tex>, что соответствует базе, в то время как при <tex> p \ne q </tex> выполнено <tex> \max(p, q ) > \gcd(p, q) </tex>, так что <tex> n > 2 </tex>.
* База
*: Истинность утверждения следует из <tex> p = q = r </tex>.
