понедельник, 18 ноября 2013
12:22

podaite ideu

все записи пользователя в сообществе Иеремиевит
Vsem privet. Podskajite hod reshenii zadachi:

nado naiti NOD chisel 15n+18 i 45n+12 (chisla vziati na obym)
Найти НОД чисел `(15n + 18)` и `(45n + 12)`, `n in NN`
n - naturalnoe chislo

@темы: Олимпиадные задачи, Теория чисел

URL
Комментарии
18.11.2013 в 18:38

Дилетант
На плечах гигантов, на спинах электронов
Поясните, пожалуйста, задачу. (Я не большой специалист, но просто чтобы было понятно). Нужно найти такое n, при котором НОД будет максимальным, или найти общий делитель, который был бы делителем этих чисел для любого n (и в некоторых случаях являлся бы НОДом)?
URL
18.11.2013 в 18:40

Иеремиевит
Дилетант, nado naiti naibolshee znacenie NODa pri lubom n
URL
18.11.2013 в 18:41

Иеремиевит
Дилетант, n - naturalnoe chislo
URL
18.11.2013 в 19:49

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Иеремиевит, naibolshee znacenie NODa pri lubom n - :upset: ... при любом или при каждом?...

Если при любом, то достаточно заметить, что 3 общий множитель обоих чисел... `15*n + 18 = 3*(5*n + 6), \ \ 45*n + 12 = 3*(15*n + 4)` ... а оставшиеся множители при `n = 1` будут взаимно простыми... `5*1 + 6 = 11, \ \ 15*1 + 4 = 19`...
URL
18.11.2013 в 22:10

Дилетант
На плечах гигантов, на спинах электронов
All_ex, я не успела на работе написать...
То ли там был совершенно реальный пример, где НОД можно было как-то выразить через n, то ли еще что-то сделать...
Например, в этом, где числа от фонаря, понятно, что для любого четного n НОД=6k.
При n=3 НОД здесь уже 21, если я правильно посчитала...
При n=5 - опять 3...
Неясно, чего хотят...
Только во втором числе в скобке не 9n, а 15n :shuffle:
URL
18.11.2013 в 22:17

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Дилетант, Только во втором числе в скобке не 9n, а 15n :shuffle: - Да... мой косяк :pom:... Спасибо поправил коммент...
URL
18.11.2013 в 23:26

Иеремиевит
All_ex, v zadanie skazano "gde n -naturalnoe chislo" - znachit pri lubom
URL
18.11.2013 в 23:31

Дилетант
На плечах гигантов, на спинах электронов
Иеремиевит, понимаете, для разных n получаются разные значения НОД.
Может быть, в каком-то конкретном случае НОД выражается непосредственно через n...
Или наоборот: в другом конкретном случае можно сказать, что он равен такому-то числу и ничему больше... Но для этого нужно видеть реальную задачу.
А здесь кроме того, что НОД представляется в виде 3k по-моему ничего сказать нельзя. Хотя, возможно, я не знаю каких-то фундаментальных вещей в теории чисел...
Вы можете привести настоящее задание?
URL
18.11.2013 в 23:33

Иеремиевит
я читал что по правилам нельзя выкладывать задания реальной олимпиады. я выложил подобный пример. хотя цифры подобрал плохо;
URL
18.11.2013 в 23:33

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Иеремиевит, v zadanie skazano "gde n -naturalnoe chislo" - znachit pri lubom совсем не обязательно... на мой взгляд, это указание на то, что `n` неотрицательное... ну, и надо выяснить как НОД этих двух чисел меняется в зависимости от `n`...
URL
18.11.2013 в 23:40

Иеремиевит
в оригинале нет общего множителя
я думаю что NOD надо выразить через n

17n+8 i 27n+3 пример больше похож на реальный(числа pri n - простые множители)
URL
18.11.2013 в 23:43

Иеремиевит
seichas ne mogy bolshe pisat' k sojaleniu (vremia vishlo). napishy zavtra okolo 20 po Moskve.
URL
18.11.2013 в 23:44

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Иеремиевит, я думаю что NOD надо выразить через n - Хм... так мы говорили об одном и том же... :upset:
в оригинале нет общего множителя - это не важно...
URL
19.11.2013 в 15:56

Иеремиевит
есть теорема NOD (a;b), где a>b = NOD(a-b;b)

Primer NOD (59;7)= NOD (52;7)= NOD (45;7)=...=NOD (10;7)= NOD (3;7) = NOD (3;4)=...=NOD (1;1)=1
URL
19.11.2013 в 15:58

Иеремиевит
All_ex, в оригинале нет общего множителя - это не важно...
это усложняет задачу
URL
19.11.2013 в 16:09

Дилетант
На плечах гигантов, на спинах электронов
есть теорема NOD (a;b), где a>b = NOD(a-b;b)
Она применима к вашим числам? Или как-то упрощается задача? Если да, то очень хорошо.
Просто, конечно, я понимаю, что и вам и нам тяжело без точного условия.

это усложняет задачу
Наоборот, упрощает на один шаг. Не нужно выносить за скобку общий множитель. Задача в любом случае сводится именно к такой.
...
Вот посмотрите еще - может чем-то поможет: ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%B0%...
URL
19.11.2013 в 16:24

Иеремиевит
для 17n+8 i 27n+3 имеем:

1) для n=0 NOD (8;3)=1
2) для n>0 - 27n+3>17n+8 - значит "есть теорема NOD (a;b), где a>b = NOD(a-b;b)" . значит NOD (17n+8;27n+3) = NOD (17n+8;10n-5)
3) теперь 17n+8>10n-5 (всегда) :lamp: значит опять эта теорема NOD (17n+8;10n-5) = NOD (7n+13;10n-5)
URL
19.11.2013 в 16:37

Иеремиевит
1) ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%B0%... posmotru i poprobyu
2) math.ru/lib/book/djvu/vinogradov.djvu :lamp: НЕ МОГУ ОТКРЫТЬ, no dymau tam est' chto-to interesnoe (§ 2. )
URL