Помогите небольшую задачку решить

← →
Hover (2006-03-16 16:10) [0]

Уже два часа сижу, никаких мыслей нет.
НОД чисел M и N = 1
Найти НОД(12N-M;5N+M), если известно, что оно больше 1

← →
oldman © (2006-03-16 16:33) [1]

Что ты подразумеваешь под НОД???
(извини, голова отказала...)

← →
Hover (2006-03-16 16:37) [2]

Наибольший общий делитель - НОД

← →
Hover (2006-03-16 16:41) [3]

Я нашел такие свойства:

НОД(a, b) = НОД(a, a + b) = НОД(a + b, b)
НОД(a, b) = НОД(a - b, b), если a > b;
НОД(a, b) = НОД(a, b-a), если b > a.

Но вот применения им найти не могу..

← →
oldman © (2006-03-16 16:50) [4]

> Уже два часа сижу, никаких мыслей нет.
> НОД чисел M и N = 1

Это значит, что N/M - не целое..., а (12N-M)/(5N+M) - целое... (при условии, что N>M)
А далее перебором... пока не надоест... хотя бы для чисел от 1 до 100... не так уж и долго...

← →
Hover (2006-03-16 17:00) [5]

То есть, если НОД(a,b)>1, то это (a/b) - обязательно целое число?

← →
oldman © (2006-03-16 17:03) [6]

Говорю же, голова не варит.
Конечно нет!
12 и 8 тому пример...

Думаем дальше...

← →
Hover (2006-03-16 17:06) [7]

Вот и я подумал, что не для всех чисел это подходит..

← →
MBo © (2006-03-16 17:22) [8]

Применив алгоритм Евклида, получаем 17, если не ошибся

← →
wHammer © (2006-03-16 17:24) [9]

алгоритм Евклида (расширенный алгоритм Евклида)

← →
oldman © (2006-03-16 17:28) [10]

получаем:

12n-m=a
5n+m=b

m=b-5n
12n+b+5n=a
17n=a+b

n=(a+b)/17
m=b-5(a+b)/17

при учете того, что a,b,m,n - целые решений не так уж много (для m и n от 1 до 100)
а дальше - визуальная проверка и решение найдено! :)))
или алгоритм нужен???
задачка похожа на олимпиадную...

← →
oldman © (2006-03-16 17:29) [11]

при учете еще и того, что a и b не могут быть четными одновременно...

← →
Hover (2006-03-16 17:38) [12]

Это и есть олимпиадная. По математике.

to MBo:
Для чисел N=3 M=2 ответ 17 подходит
НОД(34;17)=17

А как вы пришли к такому ответу?

← →
Hover (2006-03-16 17:44) [13]

to oldman:

Не совсем понял, зачем выражать числа M и N, если нужно найти их НОД?

← →
oldman © (2006-03-16 17:59) [14]

> Hover (16.03.06 17:38) [12]
> А как вы пришли к такому ответу?

Яндекс.
Поиск="как найти наибольший общий делитель"
Почти все ссылкт на алгоритм Евклида...

← →
Hover (2006-03-16 18:06) [15]

Хм. Может я что не так делаю?
(12N-M)=(5N+M)*(12/5)-(17/5)M
(5N-M)=(-17/5)M*(5/17)+5N
(-17/5)M=5N*(17/25)*(M/N)

Отсюда последний ненулевой остаток равен 5N

← →
oldman © (2006-03-16 18:12) [16]

> Hover (16.03.06 18:06) [15]
> Хм. Может я что не так делаю?
> (5N-M)=(-17/5)M*(5/17)+5N

Хм... если сократить дроби при умножении, получим:

5N-M=-M+n

:)))

> (-17/5)M=5N*(17/25)*(M/N)

Делаем ту же операцию, получаем:

(-17/5)M=(17/5)M

А вот тут со знаком проблема...

← →
default © (2006-03-16 18:21) [17]

да, 17
решение есть без всякого перебора и без алгоритма Евклида

← →
Hover (2006-03-16 18:23) [18]

to default:
Не могли бы вы написать его?

← →
SergP. (2006-03-16 18:32) [19]

> НОД(a, b) = НОД(a, a + b) = НОД(a + b, b)

Исходя из этого следует
НОД(12N-M;5N+M) = НОД(12N-M + 5N+M ;5N+M) = НОД(17N;5N+M)

Теперь смотрим на такую фигню:

NOD (N;5N+M) = NOD (N;M)=1

Следовательно НОД(17N;5N+M) = НОД(17;5N+M)
и если последнее не равно 1, то оно равно 17

← →
SergP. (2006-03-16 18:36) [20]

> SergP. (16.03.06 18:32) [19]

Думаю что должно быть очевидно что
Если NOD(a;b)=1 то NOD(a*c;b)=NOD(c;b)

это я применил в [19], если кому непонятно...

← →
SergP. (2006-03-16 18:38) [21]

> NOD (N;5N+M) = NOD (N;M)=1

С этим тоже не должно быть проблем... Все вытекает из:

> НОД(a, b) = НОД(a, b-a), если b > a.

← →
Hover (2006-03-16 18:39) [22]

> NOD (N;5N+M) = NOD (N;M)
Почему верно такое равенство?

← →
Hover (2006-03-16 18:40) [23]

Вы меня опередили с моим вопросом :)

← →
SergP. (2006-03-16 18:44) [24]

> > NOD (N;5N+M) = NOD (N;M)
> Почему верно такое равенство?

NOD (N;5N+M) = NOD(N;4N+M) =NOD(N;3N+M)=NOD(N;2N+M)=NOD(N;N+M) =NOD (N;M)

:)

Hover (16.03.06 18:23) [18]
уже не надо, думаю
хотя оно без применения свойств из [3]

Hover (16.03.06 18:23) [18]
вот, если интересно
пусть 12N-M=X_1; 5N+M=X_2; X_1=KX1, X_2=KX2, где K-наибольший общий делитель чисел X_1 и X_2
имеем: 12N-M=KX1; 5N+M=KX2; сложим почленно эти равенства, получим
17N=K(X1+X2)
если бы НОД(N,K) <> 1, то, например, из равенства 12N-M=KX1, следовало бы что M делится на этот НОД, а стало быть N и M имеют общий делитель отличный от единицы, что противоречит НОД(M,N)=1(по усл.), а значит НОД(N,K)=1
смотрим теперь на равенство 17N=K(X1+X2), левая часть должна нацело делиться на K, из условий НОД(N,K)=1 и K<>1(по усл.)] следует, что K=17

Помогите небольшую задачку решить Найти похожие ветки