Помогите разобраться, как решать такие задачи. Делимость mod

[ZARATUSTRA]

Мне бы понять, как решать задачи на тему деление с остатком, так остальные может бы и сам решил.
Может кто покажет решение хоть первых трёх?
1. Какие числа можно представить в виде разности двух квадратов целых чисел?
2. Если $p$ простое число, большее трёх, то $p^2 - 1$ делится на 24.
3. При каких $n$ число $2^n − 1$ делится на $7$?
4. Известно, что сумма нескольких натуральных чисел делится на 6. Докажите, что сумма кубов этих чисел тоже делится на 6.
5. Докажите, что если целочисленная арифметическая прогрессия содержит квадрат целого числа, то она содержит бесконечно много квадратов целых чисел.
6. Три целых числа связаны соотношением $x^2 + y^2 = z^2$. Докажите, что $x$ или $y$ делится на 3.
7. Шестизначное число делится на 7. Докажите, что, если последнюю его цифру переставить в начало, то полученное число тоже будет делиться на 7.
8. Найдите три попарно взаимно простых числа таких, что сумма любых двух из них делится на третье.
9. Докажите, что простые числа большие трёх можно записать в одном из двух видов: $6n + 1$ либо $6n-1$ , где n натуральное число.
10. Докажите, что если сумма квадратов двух чисел делится на 3, то и каждое из этих чисел тоже делится на 3.
11. Дано натуральное число $N$. К нему справа приписывают по одной цифре, кроме девятки. Докажите, что рано или поздно получится составное число.
12. Докажите, что существует бесконечно много целых чисел, которые нельзя представить в виде суммы
а) трёх кубов;
б) семи шестых степеней целых чисел.

[Tanechka]

1. Вообще умейте строить рабочие гипотезы... попытайтесь посмотреть, какие числа представимы, а какие нет. Начитывать решения нужно только в сложных задачах, и то если вы уже почувствовали её сложность и сдались. А так к олимпиадам подготовиться нельзя.
2. Во второй задаче $p^2-1$, а не то, что у вас написано... Вспоминаем опять же разность квадратов, и думаем, на что же должна делиться каждая скобка.
3. Ну блин, ну это же детский сад... или опечатка...

[ZARATUSTRA]

Прошу прощения. Сейчас подправлю условие. Копировал просто с книги, так съела некоторые данные.

[Sonic86]

В 3 достаточно знать, что $p\neq q\Rightarrow p\not\equiv 0\pmod q$. А дальше просто перебор остатков.
4. Погуглите малую теорему Ферма.
В общем правда - изложите попытки решения, а то детсад.

[ZARATUSTRA]

Так-с.
С 1 задачей вроде как справился.
Пусть $a$ - первое число, $b$-второе. Какие числа можно представить ввиде $a^2-b^2$.
$(a-b)(a+b)$ То бишь мы можем представить числа, кратные $a-b$ и $a+b$ одновременно.
Или надо как-то по-другому доказывать?
2 задача.
Для начала докажем справедливость для $5$. Начиная с 7 будем рассматривать общий случай.
$p^2-1 = (p-1)(p+1)$. Множители должны делится на $4$ и $6$.
3 задача.
Заметил, что $2^n-1$ делится на 7 при $n$, кратном $3$.
при n=3 $2^3-1:7$. при $2^{n+3}=8\cdot2^n$, $(8\cdot2^n-1):7$

Так правильно?

[Sonic86]

ZARATUSTRA в сообщении #585353 писал(а):

3 задача.
Заметил, что $2^n-1$ делится на 7 при $n$, кратном $3$.
при n=3 $2^3-1:7$. при $2^{n+3}=8\cdot2^n$, $(8\cdot2^n-1):7$

Да, на пальцах по индукции все проходит Можете еще для ясности записать формулу для всех таких $n$.

ZARATUSTRA в сообщении #585353 писал(а):

2 задача.
Для начала докажем справедливость для $5$. Начиная с 7 будем рассматривать общий случай.
$p^2-1 = (p-1)(p+1)$. Множители должны делится на $4$ и $6$.

А дальше что?

ZARATUSTRA в сообщении #585353 писал(а):

Пусть $a$ - первое число, $b$-второе. Какие числа можно представить ввиде $a^2-b^2$.
$(a-b)(a+b)$ То бишь мы можем представить числа, кратные $a-b$ и $a+b$ одновременно.
Или надо как-то по-другому доказывать?

По-другому Я переформулирую: при каких $n$ уравнение $n=a^2-b^2$ имеет решение. Здесь можно начать чисто эмпирически - поискать закономерность. А дальше все увидите.

[DjD USB]

$p^2-1=(p-1)(p+1)$ рассмотрим числа $p-1,p,p+1$ Три последовательных числа где p нечетно и не делится на 3 значит 2 числа p-1 и p+1 четных,2 последовательных четных чисел,значит одно из них делится на 2 а другое на 4.При этом либо p-1 либо p+1 делится на три.Значит $p^2-1$ при простых p больших 3 делится на 24

-- Пт июн 15, 2012 20:00:48 --

9)$p\equiv -1,1\pmod 6$ Где p простое число.

[alexo2]

12 - посмотрите по мод.9 - у 3-ей степени это 0, 1, 8. У 6-ой степени - 0 и 1. Дальше, думаю, понятно.

[DjD USB]

6)Пусть х и у не делится на 3.Тогда $x^2$ и $y^2$ будут давать остаток 1 при делении на 3. Значит $x^2+y^2\equiv 2\pmod 3$ Но $z^2\equiv 0,1\pmod 3$ Следовательно либо х либо у делится на 3

[Sonic86]

(Оффтоп)

Вот я же говорю, что легкие задачи. Но ZARATUSTRA почему-то забил

[Shadow]

alexo2 в сообщении #585514 писал(а):

12 - посмотрите по мод.9 - у 3-ей степени это 0, 1, 8. У 6-ой степени - 0 и 1. Дальше, думаю, понятно.

Не нужна шестая степень, т.к у кубов по модулю 9 остатки 0,1,-1, то числа $9k\pm 4$ уже непредставимы в виде суммы трех кубов

[DjD USB]

ZARATUSTRA в сообщении #585306 писал(а):

Мне бы понять, как решать задачи на тему деление с остатком, так остальные может бы и сам решил.

Вы же не только должны задачи решпть но и знать почему это так и как это применяется.Вот здесь написано немного на тему Сранение по модулю ну и естественно задачи к теме прилагаются http://www.trushinbv.ru/4/1/1/files/mod.pdf

[Shadow]

Аааа, извините,alexo2
Вы про подусловие б) говорили

[ZARATUSTRA]

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

(Оффтоп)

Вот я же говорю, что легкие задачи. Но ZARATUSTRA почему-то забил

(Оффтоп)

Я на это дело вообще забил. Начал 5 дней назад этим темы изучать, но что-то не идёт.

[alexo2]

Shadow в сообщении #585636 писал(а):

Аааа, извините,alexo2
Вы про подусловие б) говорили

Ну, да... И сразу видно, что все возможные сочетания слагаемых не охватывают в сумме весь нат. ряд с определенной периодичностью...
А насчет того, что ТС "забил" - зря, если чуть-чуть напрячь мозги и разобраться - ничего сложного нет. Зато будет приобретен мощный инструмент для решения различного рода задач...

Кстати, по многим задачам из списка - элементарно решаются с применением МТФ.