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

Математический форум 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
Сообщений: 4002
Cпасибо сказано: 70
Спасибо получено:
855 раз в 777 сообщениях
Очков репутации: 204

Добавить очки репутацииУменьшить очки репутации
Посмотрите, чему равен [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 ] 

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

в форуме Ряды

Anna21

3

512

23 май 2014, 13:11

Задача

в форуме Аналитическая геометрия и Векторная алгебра

Aspid

1

742

29 май 2014, 21:22

Задача

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

cornholio13

6

119

01 дек 2017, 19:50

Задача №29

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

andrei

2

182

04 дек 2017, 13:29

Задача из ЕГЭ

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

Syena

5

448

22 мар 2016, 13:49

Задача

в форуме Аналитическая геометрия и Векторная алгебра

Aspid

2

633

29 май 2014, 19:45

Задача

в форуме Оптика и Волны

Isabella

1

406

26 апр 2015, 10:22

Задача №30

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

andrei

4

193

10 дек 2017, 08:13

Задача

в форуме Начала анализа и Другие разделы школьной математики

milada

3

259

05 мар 2016, 19:58

Задача

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

blind1990

0

213

17 апр 2015, 21:36


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



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

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


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

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

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

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