Теория чисел (задачи на делимость)

[N]

Подскажите, как решить задачи. Полностью решать не надо, только натолкните на мысль

1. Найти все натуральные n, для которых НОК(n^2, 15 - n) = 36

2. Для каких натуральных чисел n НОД(3^n, 2n - 1) = 1

Заранее спасибо.

[PAV]

Вообще-то все числа $n$, для которых 36 делится на $n^2$, можно перебрать вручную.

[N]

Надо решить без перебора

[Lion]

Достаточно рассмотреть только квадраты, меньшие 16, а их всего 3.
Во второй задаче рассмотрите остатки n по модулю 3 (тоже 3 случая ).

[PAV]

Lion писал(а):

Достаточно рассмотреть только квадраты, меньшие 16, а их всего 3

По-моему, это неверно. Число $n=6$ подходит

[Lion]

Мда... глупость. Перепутал $n$ и $n^2$.
Тогда можно рассмотреть только квадраты, меньшие или равные 36. Правды, их будет уже 6.

[PAV]

N
обычно когда надо перебрать всего 6 возможностей - это перебором уже не считают. Может быть и можно придумать какую-то хитрость, которая этот перебор может сократить, но это займет больше времени, чем сам перебор.

[N]

PAV писал(а):

N
обычно когда надо перебрать всего 6 возможностей - это перебором уже не считают. Может быть и можно придумать какую-то хитрость, которая этот перебор может сократить, но это займет больше времени, чем сам перебор.

Ну чтож, значит будем делать переборам. По-другому я всю голову сломал - не знаю

P.S. Если вдруг, кто-нибудь что-нибудь придумает, то поделитесь.

[Echo-Off]

PAV писал(а):

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

Хитрость придумать можно. Достаточно рассматривать только те $n\leqslant 6$, для которых верно $n | 6$. Таких чисел уже 4

[PAV]

Скажем так, очевидно, что числа 4 и 5 перебирать не надо. Но понимание этого фактически происходит из очевидного факта, что 36 не делится ни на 5, ни на 16. Проверка этого не сложнее и не проще, чем "перебор" этих чисел.

Добавлено спустя 32 секунды:

Echo-Off опередил чуть-чуть!

[Батороев]

Если разложить число 36 на простые множители и рассмотреть возможные варианты квадратов, то получим три варианта, один из которых отсеется из-за отсутствия у числа n, равно как и у числа (15 - n), общего множителя с числами 36 и 15.

[Руст]

N писал(а):

Подскажите, как решить задачи. Полностью решать не надо, только натолкните на мысль

1. Найти все натуральные n, для которых НОК(n^2, 15 - n) = 36

2. Для каких натуральных чисел n НОД(3^n, 2n - 1) = 1

Заранее спасибо.

Если n не делится на 3, то и 15-n не делится на 3. Поэтому перебрать надо только делителей 6, делящихся на 3, т.е. n=3 и n=6. Оба значения являются решениями. А если среди целых (не только натуральных), то надо перебрать и n=-6,-3,0. Но они не дают решения.