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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

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




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Задача на делимость
СообщениеДобавлено: 20 июл 2012, 10:26 
Не в сети
Любитель математики
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 22268
Откуда: Беларусь, Минск
Cпасибо сказано: 2096
Спасибо получено:
4958 раз в 4631 сообщениях
Очков репутации: 845

Добавить очки репутацииУменьшить очки репутации
Прошу помощи в решении следующей задачи: "Докажите, что если числа [math]a[/math] и [math]b[/math] взаимно просты, то существует натуральное [math]m,[/math] для которого [math]a^m-1[/math] делится на [math]b[/math]".

Полагаю, что здесь можно рассмотреть некоторую последовательность чисел вида [math]a^m-1>b[/math] и воспользоваться принципом Дирихле. Тогда в этой последовательности обязательно найдётся число, кратное числу [math]b.[/math] Но при чём здесь взаимная простота чисел [math]a[/math] и [math]b[/math]?

Или нужно воспользоваться тем, что в условиях задачи имеем
[math]a=bq+1,[/math]

[math]a-1=bq,[/math]

следовательно, число [math]a-1[/math] кратно числу [math]b,[/math] а отсюда следует требуемое?

Извините за невежество. Всё-таки есть определённые сложности в изучении алгебры и теории чисел на исходе пятого десятка лет. :oops:

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на делимость
СообщениеДобавлено: 20 июл 2012, 10:50 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
15 май 2011, 10:27
Сообщений: 7856
Cпасибо сказано: 629
Спасибо получено:
7057 раз в 5487 сообщениях
Очков репутации: 317

Добавить очки репутацииУменьшить очки репутации
Достаточно для m взять значение [math]\varphi (b)[/math],где [math]\varphi (b)[/math]-функция Эйлера.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на делимость
СообщениеДобавлено: 20 июл 2012, 10:53 
Не в сети
Light & Truth
Зарегистрирован:
11 май 2011, 16:52
Сообщений: 4429
Cпасибо сказано: 38
Спасибо получено:
1115 раз в 923 сообщениях
Очков репутации: 409

Добавить очки репутацииУменьшить очки репутации
Это очевидное следствие т. Эйлера

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на делимость
СообщениеДобавлено: 20 июл 2012, 13:05 
Не в сети
Любитель математики
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 22268
Откуда: Беларусь, Минск
Cпасибо сказано: 2096
Спасибо получено:
4958 раз в 4631 сообщениях
Очков репутации: 845

Добавить очки репутацииУменьшить очки репутации
arkadiikirsanov
andrei
А без теоремы Эйлера никак не обойтись? Данная задача предложена в качестве упражнения к теме "Наибольший общий делитель" курса алгебры и аналитической геометрии. Теорема Эйлера в этом курсе не рассматривается.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на делимость
СообщениеДобавлено: 20 июл 2012, 15:40 
Не в сети
Light & Truth
Зарегистрирован:
11 май 2011, 16:52
Сообщений: 4429
Cпасибо сказано: 38
Спасибо получено:
1115 раз в 923 сообщениях
Очков репутации: 409

Добавить очки репутацииУменьшить очки репутации
В той ссылке, которую я вам дал, т. Эйлера доказывается, исходя из элементарных соображений. Можно повторить приведенное там док-во без ссылки на готовую т. Эйлера.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на делимость
СообщениеДобавлено: 20 июл 2012, 17:48 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
14 мар 2010, 14:56
Сообщений: 4584
Cпасибо сказано: 33
Спасибо получено:
2271 раз в 1754 сообщениях
Очков репутации: 580

Добавить очки репутацииУменьшить очки репутации
Andy. Вы правильно начали рассуждать. При [math]a > 1[/math] рассмотрите остатки от деления чисел [math]a - 1,\;a^2 - 1,\;a^3 - 1, \ldots ,\;a^b - 1[/math] на [math]b[/math]. Если среди остатков есть [math]0[/math], то нужное число найдено. В противном случае будут, по крайней мере, два числа с одинаковыми остатками ( принцип Дирихле). Тогда рассмотрите разность этих чисел и воспользуйтесь взаимной простотой чисел [math]a[/math] и [math]b[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Prokop "Спасибо" сказали:
Andy
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 6 ]

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

в форуме Теория чисел

johnson

1

416

23 ноя 2017, 20:38

Задача на делимость

в форуме Теория чисел

dakanjadatut

7

353

04 ноя 2019, 18:23

Задача на делимость

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

spins06

4

519

27 мар 2015, 01:37

Задача на делимость

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

Rollick

4

478

25 окт 2019, 21:46

Сложная задача на делимость

в форуме Задачи со школьных и студенческих олимпиад

Helios

8

894

05 окт 2016, 19:18

Задача на делимость полиномов

в форуме Теория чисел

Zdrastes

8

540

17 янв 2015, 16:04

Числовая последовательность. Задача на делимость

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

Dr_Zet

8

288

06 май 2019, 22:05

Делимость

в форуме Теория чисел

DanyaRRRR

2

444

20 июл 2017, 22:06

Не-делимость на 49

в форуме Задачи со школьных и студенческих олимпиад

Xenia1996

5

564

22 авг 2017, 00:34

Делимость

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

Igor kupryniuk

1

140

25 мар 2020, 16:06


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



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

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


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

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

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

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