Логические задачи → Последние k цифр

Комментариев: 10

1. rin пишет:
   16 ноября 2008 в 18:18
   

   Чё то не понятно, надо доказать, что если а=b(частный случай, не искажающий условий), то a^n=b^n? это и так ясно :)

2. Victor пишет:
   16 ноября 2008 в 18:41
   

   это да
   Но надо доказать для общего случая
   Тоесть а может быть и не равно b, но последние k цифр у них одинаковые

3. rin пишет:
   16 ноября 2008 в 18:54
   

   Я имел в виду, что у исходных чисел мы просто отбрасываем ненужные первые цифры. Пока не останется k последних. Т.е. а(k)=b(k)
   Почему это допустимо? Да потому, что возведение в степень это умножение, умножение происходит по извесным правилам.

4. rin пишет:
   16 ноября 2008 в 18:58
   

   Я не представляю просто, как можно придумать доказательство. Для меня эт чёт-то затруднительно :)

5. Victor пишет:
   16 ноября 2008 в 19:00
   

   В том то и суть. Это кажется интуитивно понятным и возможно даже очевидным, но нужно сформулировать строгое математическое доказательство :)

6. Andrew пишет:
   17 ноября 2008 в 15:43
   

   числа а и b можно продставить в таком виде:
   a=f*10^k+y
   b=m*10^k+y
   а стало быть, при воззведении их в степень n, получится:
   a^n=(f*10^k+y)^n
   b^n=(m*10^k+y)^n
   а дальше простой примитив, расскладываем в ряд(помоему это называется так, вроде уже подзабыл),и получается, вот что:
   ...нас интересую два последних члена...
   ...+(m*10^k)*k^(n-1)+y^n
   ...+(f*10^k)*k^(n-1)+y^n

   откуда видно, что последние k цифр будут одинаковы, т.к. число которое они состовляют. получается из одинаковых слагаемых

   P.S. у второго справа члена ещё множитель должно стоять, но я уже забыл что, уже непомню точно, но на доказательство оно не влияет

7. Victor пишет:
   17 ноября 2008 в 21:17
   

   Верно
   Но есть куда более красивое решение
   Приведу его завтра, если никто не придумает чего-то нового

8. Andrew пишет:
   18 ноября 2008 в 15:00
   

   Ну можно и иначе.
   Что харрактеризует в первую очередь числа a и b? То, что их разница дает некое число, с k нулей в конце:
   a-b=y*10^k
   Значит, чтобы решить задачу, нужно показать, что числа a^n и b^n после вычитания, тоже, дадут некое число с k нулей в конце.
   Представим числа а и b в таком виде:
   a=f*10^k+y
   b=m*10^k+y
   Найдём разницу a^n и b^n:
   a^n-b^n=(f*10^k+y)^n-(m*10^k+y)^n=....тут опять расскладываем на ряды...=
   =...y^n сокращается...=...в итоге, в каждом оставшемся члене есть общий множетель 10^k...=
   =...выносим его за скобки и получаем...=10^k(...тут всякая фигня...)
   В результате мы показали, что разница a^n и b^n дает некое число с k нулей в конце.

9. Victor пишет:
   18 ноября 2008 в 19:10
   

   Ну, можно и ещё проще :)
   Как вы верно заметили, последние k цифр числа a-b - нули
   a^n - b^n = (a-b)(неполный_многочлен_степени_n-1)
   так как число а^n - b^n делится на a-b, последние k его цифр - нули
   Значит, последние k цифр у чисел а и b совпадают

10. Virtus пишет:
    2 сентября 2011 в 02:25
    

    Остатки от деления на натуральное N образуют кольцо, доказывается элементарно
    a=b(mod N) => a^n=b^n(mod N). Равенство последних k цифр - частный случай при N=10^k

Комментировать!