Доказать делимость числа на 7

sergeyvid

^10+10^10^2+10^10^3+...+10^10^10
аа?
сестренке в школе дали ее

fift

ошибка, оно не делится на 7

sergeyvid

всю ночь бился - так ни к чему и не пришел
может и не делиться, но нужны доказательства!

stm5345716

^6 = 1 (mod 7 поэтому надо найти остатки от деления 10^k на 6. 10^k - чётное число, сравнимое с 1 по модулю 3, значит, оно даёт остаток 4 по модулю 6 для каждого k=1,2,3,... Поэтому искомое число сравнимо с 10*10^4=10^5 = 5 mod 7

juliya21

Вы просто немного неправильно условие поняли, ну или дали его вам неправильно. Если считать как (10^10)^k, то делится.

iri3955

дали неправильно. ^ - единственная операция с правым приоритетом

Waleri58

а что разве нельзя решить так:
вычислить остаток деления числа 10*10 на 7
a = 10*10 mod 7,
а потом вычислить остатки a^k mod 7 k=1,2,3...10,
а потом сложить остатки и получить число, делящееся на 7?

kachokslava

^10 mod 7 = 3^10 mod 7 = (3^5)^2 mod 7 = (243)^2 mod 7 = (210+28+5)^2 mod 7 = 25 mod 7 = 4
1) 4 mod 7 = 4
2) 16 mod 7 = 2
3) 64 mod 7 = 1
4) 256 mod 7 = 4
5) 2
6) 1
7) 4
8) 2
9) 1
10) 4
4+2+1+ (7)
4+2+1+ (7)
4+2+1+ (7)
4 = не делится.

fift

Поясните пожалуйста решение.

kachokslava

что тут непонятного?

juliya21

Короче, если считать, что (10^10)^k, то это геом. прогрессия, ее сумма равна 10^10*10^10)^10-1)/(10^10-1). 10^10=10^6*10^4=10^4=3^4=9^2=4(mod 710^6 mod 7 = 1 по теореме Ферма). Поэтому 10^10-1 на 7 не делится и 10^10 тоже. Поэтому исходное число делится на 7 тогда и только тогда, когда делится (10^10)^10-1. (10^10)^10-1=4^10-1=4^4*4^6-1=4^4-1=8^2-1=0(mod 74^6 mod 7 = 1 по теореме Ферма). Поэтому наше число тоже желится на 7.
Если считать, как 10^(10^k то правильно написал, что остаток равен 5. Что там написал, я и сам не понял

maxbut

неа, все-таки 4, тож через сравнения по модулю 7 считал
2: 4^4<>8^2, 4^4=16^2=4(mod 7)

juliya21

Опа, и впрямь не равно, старею...

Waleri58

поясняю то, что написал:
a ^ d = (b * k + c) ^d = c^d (mod k) - это ясно, если выписать сумму в бином Ньютона.
дальше шло последовательное вычисление степеней остатков (10^10)^k , тут опирались на то, что a mod c * b mod c = a *b mod c
а потом сложили остатки и получили некоторое число - его остаток равен остатку числа в условии.
а я, кстати, вообще предлагал в столбик посчитать первый остаток - чтоб уж совсем по-школьному
Оставить комментарий
Имя или ник:
Комментарий: