Тема: Помогите решить задачку!

  1. #1
    Помогите решить задачку, пожалуйста!

    Найти остаток от деления (3 в степени 2007) на 2007.

    Спасибо!!
    Таити, Таити - нас и здесь неплохо кормят!

  2. Интересное на cofe.ru
  3. #2

  4. #3
    Татта, а подробности можно? У меня никак не выходит 3 в степени 2000!
    Таити, Таити - нас и здесь неплохо кормят!

  5. #4
    Татта ,остаток от деления на 2007 не может быть больше 2007

  6. #5
    Foufi
    У меня получается 180, но решение не слишком красивое, увы. Может, правда наврал где?

  7. #6
    Foufi
    Так и есть, наврал: остаток равен 1620. Я зачем-то сократил 1620/2007 до 180/223

    Решение такое.
    1) 2007 = 9*223 (где 223 - простое число)
    2) Используем малую теорему Ферма: Для всякого простого p и натурального a (a^p - a) делится на p
    3) Представляем 3^2007 в виде (3^9)^223 - 3^9 +3^9
    Жирная выделенная часть делится и на 9 (очевидно) и на 223 (см. пункт 2)
    Следовательно, задача сводится к нахождению остатка от деления последнего слагаемого 3^9 (=9*3^7=9*2187) на 2007 ==> 9*180=1620

    Вроде бы так? Но решение все-же корявенькое

  8. #7
    Рядовой читатель
    Спасибо вам огроменное!!!! Про теорему Ферма я и не вспомнила!!
    Таити, Таити - нас и здесь неплохо кормят!

Социальные закладки

Социальные закладки

Ваши права

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

Наши проекты

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