Задача по теории чисел

serengeti

видимо, свойство такое в сессию тупить. некоторые простые вопросы просто в тупик ставят. помогите, плиз?
1. d=(a,b z|a, z|b. почему из этого следует z|d?

sdserg

d=ax+by(в силу алгоритма евклида)
правая часть делится на z,значит и левая тоже

NHGKU2

a = zk = dn
b = zl = dr
z k/n = a/n = d
z l/r = b/r = d
z, d — целые, следовательно, k/n = l/r целое.
Если k/n = l/r = m, то d = zm, т.е. z|d.

serengeti

d=ax+by
именно для доказательства этого факта и нужно первое утверждение

serengeti

z, d — целые, следовательно, k/n = l/r целое
почему так? контрпример - 2*(3/2)=3
тут как-то используется то, что d наибольший. но как?

serengeti

интересно, в википедии это свойство нод (делимость на любой общий делитель) используется в качестве
определения. как показать его эквивалентность определению как максимум среди всех делителей (в одну
сторону очевидно)?

NHGKU2

Да, фигню написал
На самом деле это очевидно, если написать разложение a и b в произведение степеней простых (по основной теореме арифметики). Тогда наименьший общий делитель - это произведение общих множителей в степени, равной минимуму из его показателей степени в a и b, а любой общий делитель (в т.ч. z есть произведение общих множителей в степени, большей или равной минимуму из его показателей степени в a и b.

sdserg

либо от противного
пусть z делится на d с остатком,напиши чему при этом равно a и b,знаем что они делятся на z,и получится,что остаток ноль.

serengeti

прикол в том, что факт разложения нода в линейную комбинацию а и б и делимости на все общие делители
используется в доказательстве основной теоремы арифметики
ладно, пойдем через алгоритм Эвклида, оттуда получим разложение нода и все остальное. но вопрос
интересный. в лекциях Нестеренко то, что нод делится на все общие делители, полагается очевидным, а я
вот с ходу не смог показать

serengeti

а вот это правильное рассуждение, спасибо. первый вопрос отпал

griz_a

Что-то я не понял
z=kd+r
a=mz
b=nz
a=mkd+mr
b=nkd+nr
d|mr, d|nr => почему r=0?
Ты, наверное, описался. d делится на z c остатком.
d=zk+r
a=md=mzk+mr
b=nd=nzk+nr
z|mr
z|nr
Снова уперся

kinglion

Факт очевидный. Например используя разложение a=p1^l1*p2^l2*...*ps^ls.
В своем решении ты не используешь (в полной мере) d = (a,b)

griz_a

Нельзя его использовать, основная теорема арифметика через это и доказывается. уже писали.
Можно доказать через Евклида, но это другое док-во.
Свое доказательство у меня, кажется, есть, я пытаюсь понять это (пока проверю свое)

kinglion

Разложение нельзя использовать? Ок. И нафиг не надо.
Тогда метод "пристального взгляда"(т.е. вообще выкладок делать не надо):
z|a, z|b => z|(a,b)
 
З.Ы. Подказка. Что такое (a,b) ?

griz_a

Наибольшее целое число, делящее a и b, но зря ты пытаешься упирать на очевидность.
Это очевидно, но не вполне тривиально.

sdserg

да,я ошиблась
насколько я понимаю дело было так:
рассматривается множество M = {m=ax+by|m>0}
d= (a,bтогда, для любого m из M d|m
если z минимальное из M,то d делит z как всякое из М.дальше для м произвольного из М рассуждения о том что z|m.
и тут вывод что для m произвольного вида m=ax+by можно сказать,что z|a и z|b,что понятно.т к z|m,а значит z|d т к:
m=dkx+dry,где x y вообще говоря произв,а значит kx+ry тоже произв и d не делит r и k,отсюда z|d

griz_a

где x y вообще говоря произв,а значит kx+ry произвольно
С этого места поподробней, пожалуйста. Там еще существенно тогда, что они взаимнопросты и это та же теорема для d=1.
По-моему, там идет так - z|m
Но a,b in M
=> z|a,z|b=>z|d.
Вот и используется тот самый факт

sdserg

нет,я не понимаю,легко можно привести пример x y ,что d не поделит kx+ry,а у нас утвер должно выполняться всегда,отсюда делаем вывод,что z будет делить d

griz_a

А зачем d должно делить kz+xy?
Кстати, как легко?

sdserg

z число фиксированное,оно не может через раз то d то kx+ry делить

sdserg

не должно=)
поэтому z|d

griz_a

Ничего не понял
z|d(kx+ly k,l - фикс, взаимно простые, x,y - любые.
Почему z|d

sdserg

возьми r+k и к+2k,хотя бы одно из них не делится на d
так как они взаимно просты

griz_a

Если я правильно тебя понял, то ты имеешь ввиду, что любое число вида , x>1 не делит все числа M, значит z|d. Почему? Это то же утверждение, что и автор треда предлагал Тут надо следить за тем, что очевидно =)

sdserg

>возьми r+k и к+2k,хотя бы одно из них не делится на d
>так как они взаимно просты
с этим тоже не согласен?

griz_a

согласен. Что дальше. Напиши все рассуждения по порядку начиная с места, где ты отклоняешься от исходного доказательства

sdserg

Ничего не понял
z|d(kx+ly k,l - фикс, взаимно простые, x,y - любые.
Почему z|d
z|d(kx+ly)-это мы знаем
пусть z не делит d
я могу сказать,что тогда z|(kx+ly)?
(причем при любых x и y)

griz_a

Нет, конечно. Это неверное утверждение, не только неочевидное.

griz_a

|6
6 не делит 2
Значит 6|3?

sdserg

значит надо как-то использовать условие минимальности z
пока хз как..

sdserg

дел

sdserg

а если z и d сократить на общий делитель,то kx+ly должно делиться на фиксир число

aktauast

Какая размерность у оптической плотности (А и у пропускания (Т) ?

griz_a

Почему из того, что z|d(kx+ly)=>z/НОД(z,d)|(kx+ly)?
Кстати, я придумал.
d|z=>d<=z
Но тогда z - общий делитель a,b, а z>=d => z=d

sdserg

вот именно раньше доказали,что d делит z
на него вообще можно сократить,и получим что с|(lx+ky)
а твои рассуждения действительно заканчивают нестеренковскую лемму=)

griz_a

Да, по-твоему, видимо, тоже выходит...

sdserg

примерно килограммы делить на теслу..
такое то не знать..

serengeti

p_1, p_2, ..., p_n, p_{n+1} - первые n+1 простых чисел, отсортированные по возрастанию. как
показать, что p_{n+1} не больше наименьшего простого делителя числа p_1*p_2*...*p_n + 1?

griz_a

А подумать?
Рассмотрим наименьший простой делитель числа p_1*p_2..*p_n+1
Он не равен ни одному из p_1,..p_n, т.к. с ними взаимно прост. Но он простой. Значит наименьшее простое число после первых n не превосходит его

serengeti

точно, спасибо. вчера ночью никак не мог сообразить. а сейчас все очевидно
зы а думать я пытался, честно

svetik70

Гм, извините, но доказали утверждение в первом посте или нет? Прочитал тему, но потерялся в ваших кусках док-ва.

stm5345716

Гм, извините, но доказали утверждение в первом посте или нет? Прочитал тему, но потерялся в ваших кусках док-ва.
Доказали
Кстати, я придумал.
d|z=>d<=z
Но тогда z - общий делитель a,b, а z>=d => z=d

svetik70

Кстати, я придумал.
d|z=>
А почему d|z?

serengeti

я успокоился на таком рассуждении:
док-ть: a, b, d, z суть из N. d = (a,b z|a, z|b => z|d
док-во: запишем
a = a_d*d, b = b_d*d, a = a_z*z, b = b_z*z,
при этом, т.к. d наибольший, (a_d,b_d) = 1 (иначе это число домножим к d, получим больший од)
т.к. d наибольший од => z <= d => имеем d = q*z + r. тогда
a = a_d*q*z + a_d*r и b = b_d*q*z + b_d*r. предположим, что 0 < r < z
тогда z|a_d*r и z|b_d*r. поскольку r < z => (r,z) = g <= r => (a_d,b_d) > 1
противоречие с тем, что d - наибольший од

serengeti

апд: фигню написал

stm5345716

А почему d|z?
Потому что этот пост относился к док-ву того, что d=ax+by, из которого следует утверждение в первом посте. z определялось как минимальное натуральное число вида z=ax+by.

svetik70

Ае, я всё понял. Да, безупречное док-во.

stm5345716

...тогда z|a_d*r и z|b_d*r. поскольку r < z => (r,z) = g <= r => (a_d,b_d) > 1 ...
А поподробнее? Это неочевидно

svetik70

тогда z|a_d*r и z|b_d*r. поскольку r < z => (r,z) = g <= r => (a_d,b_d) > 1
По-моему, тут слабое место в твоём варианте док-ва. Почему, собственно, решено, что (a_d,b_d) > 1?

serengeti

да, не расписал вот какое соображение:
т.к. z > r, то z|a_d*r означает, что z = z_1*z_2, где z_1|a_d, z_2|r
для определенности полагаем z_2 = (r,z) < z => z_1 > 1
аналогично получаем, что z_1|b_d => (a_d,b_d) = z_1 >1
теперь хорошо?

svetik70

т.к. z > r, то z|a_d*r означает, что z = z_1*z_2, где z_1|a_d, z_2|r
Придираюсь к этому. z = z_1*z_2, где z_2 = (r, z) — это понятно. Но почему z_1|a_d?

griz_a

Лучше воспользуйся простым приведенным доказательством. Тут очень легко посчитать что-то очевидным, что "еще не очевидно"
Оставить комментарий
Имя или ник:
Комментарий: