Элементарная теория чисел

[Whitaker]

Здравствуйте!
Интересует такой вопрос.
Пусть у нас есть множество $A=\{a+1, a+2, ..., a+3n\}$
Как определить сколько чисел в множестве $A$ дают при делении на $3$ остатки $0, 1, 2$?
Хотелось бы это понять через следующий факт:
Количество чисел в ряду $1, 2, 3, .... M$, которые делятся на $m$ равно $\Big[\dfrac{M}{m} \Big]$.
С уважением, Whitaker.

[SpBTimes]

а вы знаете такую штуку, как вычеты?

[Whitaker]

А если сделать так: Если из множества $A$ отнять почленно элемент $a$ тогда получим: множество $A-a=\{1, 2, ...., 3n \}$ тогда количество чисел, делящиеся на 3 равно $\Big[\dfrac{3n}{3} \Big]=n$.
Найдем количество чисел, которые при делении на $3$ дают в остатке $1$. Для этого из множества $A$ почленно вычтем число $3k+1$ получим множество $A-(3k+1)=\{a-3k, a-3k+1, ...., a-3k+3n-1 \}$. Тогда нам надо найти всего лишь в $A-(3k+1)$ количество чисел делящиеся нацело на $3$. А это количество равно величине $\Big[\dfrac{a-3k+3n-1-(a-3k)+1}{3} \Big]=n$.
Скажите пожалуйста правильно ли я рассуждаю?

[SpBTimes]

Очень внимательно не вчитывался, но это и есть некая идеология вычетов.

[Whitaker]

Мне бы хотелось узнать правильно ли я рассуждаю
P.S. А про вычеты я не так уж много пока знаю. Всего лишь элементы.

[SpBTimes]

Рассуждаете верно.
Теперь рассмотрев числа, котораы дают остаток 2, вы получите, что их тоже n. Сумма будет 3n.

[Whitaker]

Уважаемый SpBTimes!
Хочу у Вас спросить. Можно ли аналогичное рассуждение проводить для случая, когда множество $A$ любой размерности(мощности)? Например $3n+2$ или $4n+2$ ?

[SpBTimes]

Аналогичные можно, ответ получиться в зависимости от а

[Whitaker]

Уважаемый SpBTimes благодарю Вас за внимание и за помощь.
С уважением, Whitaker.

[SpBTimes]

Whitaker
можно без уважаемого и без Вы

[Whitaker]

Еще такой вопрос.
Как доказать использую теорему, что количество чисел в ряду $m, m+1, m+2, ... M$ делящиеся на $k$ равно $\Big[\dfrac{M-m+1}{k} \Big]$?

Теорема:
Количество чисел в ряду $1, 2, 3, .... M$, которые делятся на $m$ равно $\Big[\dfrac{M}{m} \Big]$.

[SpBTimes]

Ну рассмотрите такое множество: $1, 2, 3, ..., m+1, m+2, ... M$
Согласно теореме, кол-во чисел, делящихся на k равно: $[\frac{M}{k}]$
Но нас не интересует первые $m - 1$ чисел, то есть, где $[\frac{m - 1}{k}]$ делящихся. То есть:
$n = [\frac{M}{k}] - [\frac{m - 1}{k}]$
Последнее же равенство обосновывается тривиально.

[Whitaker]

А да всё понятно
Благодарю

[Sonic86]

Whitaker в сообщении #483605 писал(а):

количество чисел в ряду $m, m+1, m+2, ... M$ делящиеся на $k$ равно $\Big[\dfrac{M-m+1}{k} \Big]$?

Это не совсем так. Оно может быть на 1 больше, например: $k=3, m=3, M=6$: в списке $3;4;5;6$ ровно $2$ числа делятся на $3$, а по формуле будет $1$. Т.е. число делящихся чисел не только от длины интервала зависит.

-- Сб сен 17, 2011 04:30:52 --

Whitaker в сообщении #483586 писал(а):

Пусть у нас есть множество $A=\{a+1, a+2, ..., a+3n\}$
Как определить сколько чисел в множестве $A$ дают при делении на $3$ остатки $0, 1, 2$?

Здесь можно так: разобьем множество $A$ последовательно на классы мощности 3: $\{ a+1;a+2;a+3\}; \{ a+4;a+5;a+6\}; ... ;\{ a+3n-2;a+3n-1;a+3n\}$. В каждом таком классе, очевидно, ровно одно число делится на $3$, а всего классов $n$, значит всего таких чисел - ...

-- Сб сен 17, 2011 04:32:07 --

Whitaker в сообщении #483593 писал(а):

Хочу у Вас спросить. Можно ли аналогичное рассуждение проводить для случая, когда множество $A$ любой размерности(мощности)? Например $3n+2$ или $4n+2$ ?

Вот для любого $A$ такое рассуждение, опять же, не прокатит - иногда отличие на 1.

[Whitaker]

Sonic86 в сообщении #483644 писал(а):

Whitaker в сообщении #483605 писал(а):

количество чисел в ряду $m, m+1, m+2, ... M$ делящиеся на $k$ равно $\Big[\dfrac{M-m+1}{k} \Big]$?

Это не совсем так. Оно может быть на 1 больше, например: $k=3, m=3, M=6$: в списке $3;4;5;6$ ровно $2$ числа делятся на $3$, а по формуле будет $1$. Т.е. число делящихся чисел не только от длины интервала зависит.

-- Сб сен 17, 2011 04:30:52 --

Whitaker в сообщении #483586 писал(а):

Пусть у нас есть множество $A=\{a+1, a+2, ..., a+3n\}$
Как определить сколько чисел в множестве $A$ дают при делении на $3$ остатки $0, 1, 2$?

Здесь можно так: разобьем множество $A$ последовательно на классы мощности 3: $\{ a+1;a+2;a+3\}; \{ a+4;a+5;a+6\}; ... ;\{ a+3n-2;a+3n-1;a+3n\}$. В каждом таком классе, очевидно, ровно одно число делится на $3$, а всего классов $n$, значит всего таких чисел - ...

-- Сб сен 17, 2011 04:32:07 --

Whitaker в сообщении #483593 писал(а):

Хочу у Вас спросить. Можно ли аналогичное рассуждение проводить для случая, когда множество $A$ любой размерности(мощности)? Например $3n+2$ или $4n+2$ ?

Вот для любого $A$ такое рассуждение, опять же, не прокатит - иногда отличие на 1.

Спасибо большое Sonic86.
Получается, что точно определить количество делящихся на некоторое $m$ определить нельзя. А я ведь думал то, что я написал верно