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

Математический форум 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
Сообщений: 3836
Cпасибо сказано: 69
Спасибо получено:
821 раз в 745 сообщениях
Очков репутации: 201

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

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

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

andrei

1

186

13 авг 2017, 17:59

Задача № 23

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

andrei

6

191

15 авг 2017, 06:51

Задача

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

Isabella

1

397

26 апр 2015, 10:22

Задача

в форуме Комбинаторика и Теория вероятностей

DmitriyONE

3

142

17 авг 2017, 21:45

Задача

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

VHS tape

3

190

08 янв 2016, 11:30

Задача №24

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

andrei

1

183

24 авг 2017, 15:41

Задача

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

Zed

0

314

09 янв 2016, 11:46

Задача

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

blind1990

0

201

17 апр 2015, 21:36

Задача

в форуме Алгебра

Zatamon

2

264

14 янв 2016, 15:01

Задача

в форуме Ряды

ban

0

89

19 окт 2016, 14:01


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



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

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


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

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

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

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