Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Задача на НОД
СообщениеДобавлено: 07 май 2015, 16:14 
Не в сети
Продвинутый
Зарегистрирован:
24 апр 2013, 22:37
Сообщений: 58
Cпасибо сказано: 4
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Помогите советом как решить..
Докажите, что если [math](a,b)=1[/math], то наибольший общий делитель чисел [math]a+b[/math] и [math]a^2+b^2[/math] равен либо 1, либо 2
Был вариант по алгоритму Евклида.. Но чего-то не могу поделить [math]a^2+b^2[/math] на [math]a+b[/math].
Возможно надо использовать свойство НОД? но какие не могу сообразить...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на НОД
СообщениеДобавлено: 07 май 2015, 16:30 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3130
Cпасибо сказано: 53
Спасибо получено:
686 раз в 619 сообщениях
Очков репутации: 199

Добавить очки репутацииУменьшить очки репутации
Посмотрите, чему равен [math]\gcd(a^2-b^2, a^2+b^2)[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на НОД
СообщениеДобавлено: 07 май 2015, 18:08 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 13:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
hint: [math](\forall k\in\mathbb{Z})\gcd(x,y)=\gcd(x,y-kx)[/math] (проблемы с отображением формул пусть разбирает мегаодмин)

briz писал(а):
Но чего-то не могу поделить [math]a^2+b^2[/math] на [math]a+b[/math].
А чего не можете? все прекрасно делится, рассматривайте [math]a[/math] как переменную, [math]b[/math] - как константу.

swan писал(а):
Посмотрите, чему равен [math]\gcd(a^2-b^2, a^2+b^2)[/math]
Эта подсказка создает впечатление необходимости некоторой малопонятной догадки, в то время как здесь все совершенно алгоритмично: [math]b\equiv -a \pmod {a+b}[/math] :O:

Ппц, и эта формула не работает...
Тест: [math]x^2\equiv x^2[/math]
Ахах, сцайт разваливается...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на НОД
СообщениеДобавлено: 02 сен 2015, 03:11 
Не в сети
Начинающий
Зарегистрирован:
31 авг 2015, 22:26
Сообщений: 4
Cпасибо сказано: 0
Спасибо получено:
3 раз в 2 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
briz писал(а):
Помогите советом как решить..
Докажите, что если [math](a,b)=1[/math], то наибольший общий делитель чисел [math]a+b[/math] и [math]a^2+b^2[/math] равен либо 1, либо 2
Был вариант по алгоритму Евклида.. Но чего-то не могу поделить [math]a^2+b^2[/math] на [math]a+b[/math].
Возможно надо использовать свойство НОД? но какие не могу сообразить...


Воспользуемся следующим свойством НОД'а двух натуральных чисел:

[math]\gcd (a,b) = \gcd (a,b - a) \Leftrightarrow \gcd (a + b,{a^2}+{b^2}- (a + b))[/math]


Число [math]{a^2}+{b^2}- (a + b)[/math] делится на два, так как [math]a(a - 1) + b(b - 1)[/math] каждое из слагаемых есть два последовательных числа, среди которых одно должно быть четным. Теперь нам нужно найти [math]\gcd (a + b,2k)[/math], где [math]k[/math] нечетное число. Осталось рассмотреть [math]2[/math] случая:

1) Если [math]a[/math] и [math]b[/math] разной четности то их сумма будет нечетным числом. Поэтому
[math]\gcd (a + b,{a^2}+{b^2}) = \gcd (2m + 2n + 1,{(2m + 2n + 1)^2}- (4m + 8mn)) = \gcd (2m + 2n + 1,(2n + 1)4m) = 1[/math]


2) Если [math]a[/math] и [math]b[/math] оба нечетны, то их сумма будет четным числом. Имеем:
[math]\gcd (a + b,{a^2}+{b^2}) = \gcd (2(m + n + 1),{(2(m + n + 1))^2}- (8mn + 2(m + n + 1))) = \gcd (2(m + n + 1),8mn) = 2[/math]


По условию случай когда [math]a[/math] и [math]b[/math] оба четные невозможен.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задача

в форуме Теория вероятностей

viktorinka

3

92

03 мар 2017, 15:55

Задача №18

в форуме Интересные задачи участников форума MHP

andrei

4

177

30 мар 2017, 15:33

ТВ задача

в форуме Теория вероятностей

cincinat

2

101

12 дек 2015, 20:01

Задача

в форуме Экономика и Финансы

ryabec

3

227

01 окт 2015, 22:50

Задача

в форуме Геометрия

afwfw

4

325

01 апр 2016, 18:18

Задача

в форуме Дифференциальное исчисление

photographer

2

108

31 мар 2016, 08:35

Задача

в форуме Дискретная математика, Теория множеств и Логика

cincinat

3

85

30 мар 2016, 09:23

Задача по РЦБ

в форуме Экономика и Финансы

viktorcb

4

140

20 мар 2015, 01:17

Задача

в форуме Теория вероятностей

Alina55577

3

165

31 май 2015, 00:50

Задача

в форуме Теория вероятностей

JONI

1

193

24 май 2012, 21:42


Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 14


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved