Делимости

[taskovn]

Здравейте,може ли някой да ми помогне със следните 2 задачки:

1)Да се намерят последните 3 цифри на числото 2^2010
-Проблемът ми тук е че 2 и 1000 не са взаимно прости и нз как да процедирам с функцията на Ойлер.

2)Пресметнете колко са естествените числа. ненадминаващи 2008, които се делят на 3 и на 4, но не се делят на 7 и на 8?

Мерси предварително

[Реклама]

[marshal]

Начи:

1) Трябва да следиш само последните три цифри при степенуването.
Намери цикъла на повтаряемостта на последните три цифри при степените на двойката.
И изчисли коя ще е 2010-тата степен.

2) Нека числото е A.
3| a
4| a

8 не дели а
= > а се съдържа само от една четворка.
Първото число е 3.4, второто е 3.3.4 ....
Айде нататъка сам...

[Пафнутий]

Написаното от marshal за 2-рата задача е грешно. От условието следва, че двойката участва от 2-ра степен в каноничното разлагане на числото, а за другите прости делители няма др условие освен поне един от тях да е [tex]3[/tex] и да няма [tex]7[/tex], т.е числото [tex]3.4.5[/tex] върши работа. Понеже искаше хинт- използвай, че броя на числата от [tex]1[/tex] до [tex]m[/tex], кратни на [tex]n[/tex] са [tex]\lfloor \frac{m}{n} \rfloor[/tex]

[marshal]

Не съм съобразил за другите прости делители...

[taskovn]

Благодаря и на двама ви.Незнайно защо не мога да давам положителни гласове,затова не съм ви дал.
Колкото до първа задача

[tex]2^{2010}[/tex] = ?

(2,1000) = 2

1000= [tex]2^{3}[/tex]*[tex]5^{3}[/tex]=8*125

[tex]\varphi {(125)}[/tex] =100

[tex]2^{100}[/tex][tex]\equiv[/tex] 1(mod 125) => [tex]2^{2000}[/tex][tex] \equiv[/tex] 1(mod125)

[tex]2^{10}[/tex] = 1024 =>[tex] 2^{2010}[/tex][tex]\equiv[/tex] 24(mod125)

8|[tex]2^{2010}[/tex]

8|24

=> 8|[tex]2^{2010}[/tex]-24

=>[tex]2^{2010}[/tex][tex]\equiv[/tex] 024(mod1000)


Как ви се струва решението като формулировка?

[marshal]