Mam następujące zadanie:
Rozważmy następującą metodę sprawdzania podzielności dodatnich liczb całkowitych zapisanych w systemie dziesiętnym przez \(\displaystyle{ 7}\): Załóżmy, że badana liczba jest k-cyfrowa. Jeśli \(\displaystyle{ k \leq 3}\), to podzielność sprawdzamy bezpośrednio. W przeciwnym razie badaną liczbę zastępujemy nową, uzyskaną przez odjęcie podwojonej ostatniej cyfry od liczby złożonej z pierwszych \(\displaystyle{ k-1}\) cyfr, i ewentualnie powtarzamy całą operację.
PRZYKŁAD: \(\displaystyle{ 20102 \rightarrow 2010 - 2 \cdot 2 = 2006 \rightarrow 200 - 2 \cdot 6 = 188}\); ta ostatnia liczba nie jest podzielna przez \(\displaystyle{ 7}\), więc wnioskujemy, że początkowa również.
(a) Udowodnij poprawność tej metody.
(b) Podaj prosty wzór pozwalający wyznaczyć resztę z dzielenia początkowej liczby przez \(\displaystyle{ 7}\) na podstawie końcowej liczby \(\displaystyle{ x}\) oraz liczby iteracji \(\displaystyle{ i}\).
Rozpisałem sobie liczbę jako sumę cyfr dziesiętnych pomnożonych przez odpowiednią potęgę \(\displaystyle{ 10}\) oraz tę drugą liczbę (złożoną z \(\displaystyle{ k-1}\) cyfr), ale nie wiem co dalej. Proszę o pomoc.
Podzielność przez 7 - udowodnij metodę
-
- Użytkownik
- Posty: 42
- Rejestracja: 23 sie 2013, o 15:33
- Płeć: Mężczyzna
- Podziękował: 2 razy
- Pomógł: 6 razy
Podzielność przez 7 - udowodnij metodę
Na dziś mogę powiedzieć tylko, że dla liczby \(\displaystyle{ k=\sum_{n=0}^{N}c_n10^n}\)
jeśli zachodzi, że
\(\displaystyle{ 7|\sum_{n=1}^{N}c_n10^{n-1} -2c_0}\)
wtedy również \(\displaystyle{ 7|10(\sum_{n=1}^{N}c_n10^{n-1} -2c_0)=\sum_{n=1}^{N}c_n10^{n} -20c_0}\)
a ponieważ \(\displaystyle{ -20c_0 \equiv c_0 \mod 7}\)
to także \(\displaystyle{ 7|\sum_{n=1}^{N}c_n10^{n} +c_0=k}\).
jeśli zachodzi, że
\(\displaystyle{ 7|\sum_{n=1}^{N}c_n10^{n-1} -2c_0}\)
wtedy również \(\displaystyle{ 7|10(\sum_{n=1}^{N}c_n10^{n-1} -2c_0)=\sum_{n=1}^{N}c_n10^{n} -20c_0}\)
a ponieważ \(\displaystyle{ -20c_0 \equiv c_0 \mod 7}\)
to także \(\displaystyle{ 7|\sum_{n=1}^{N}c_n10^{n} +c_0=k}\).