Если $%НОД(A,B) = 1$%, то для любого $%N \ge A \cdot B - A - B +1$% существуют $%k,m$% большие нуля, что $%N = kA +mB$%.

задан 19 Июл '15 20:33

изменен 19 Июл '15 20:36

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
2

Числа $%0,A,2A,...,(B-1)A$% дают $%B$% различных остатков при делении на $%B$% ($%A$% и $%B$% взаимно просты!), поэтому найдётся такое $%k$%, что $%N\equiv kA\pmod B$%. Тогда $$m=\frac{N-kA}{B}\ge\frac{AB-A-B+1-(B-1)A}B=\frac{-B+1}B>-1\Rightarrow m\ge0.$$

ссылка

отвечен 19 Июл '15 21:10

изменен 19 Июл '15 23:46

1

@EdwardTurJ: самое последнее неравенство неверно -- дробь получается в общем случае отрицательной. Видимо, имелось в виду, что она строго больше -1, и тогда m как целое число уже будет неотрицательным.

В условии, правда, говорится о положительных числах, но такие не всегда найдутся. Скажем, при A=3, B=5 числа N=9 или N=10 по-другому не представить.

(19 Июл '15 22:53) falcao

@falcao: Спасибо, подправил.

(19 Июл '15 23:47) EdwardTurJ
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,293
×802

задан
19 Июл '15 20:33

показан
728 раз

обновлен
19 Июл '15 23:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru