matematikk.net

Gitt mengden[tex]\left \{ 1,11,111,...,(\frac{10^{2007}-1}{9}) \right \}[/tex]

Bevis at minst et av tallene i mengden er delelig med 2007.

Dolandyret wrote:Gitt mengden[tex]\left \{ 1,11,111,...,(\frac{10^{2007}-1}{9}) \right \}[/tex]
Bevis at minst et av tallene i mengden er delelig med 2007.

Prøver meg:
Antar M = 111...111, og at

[tex]M \equiv 0 \pmod{2007}[/tex]

Vi vet at: [tex]2007=3^2*223[/tex]
og vha Eulers teorem og totientfunksjon,
[tex]a^{\phi(n)} \equiv 1 \pmod{n}[/tex]
har at:
[tex]\phi(223) = 222[/tex]
kan så skrive:
[tex]10^{\phi(223)} \equiv 10^{222} \equiv 1 \pmod{223}[/tex]
dvs
[tex]10^{222} - 1 \equiv 0 \pmod{223}[/tex]
og
[tex]10^{222} - 1 =9*N[/tex]
da
[tex]gcd(9, 223) = 1[/tex]
så er
[tex]N \equiv 0 \pmod{3}[/tex]
og
[tex]N \equiv 0 \pmod{223}[/tex]
og
[tex]N \equiv 0 \pmod{3*223}[/tex]

her har jeg litt problemer med argumentasjonen, men hvis:

[tex]M=N*x[/tex]
og
[tex]x \equiv 0 \pmod{3}[/tex]
så blir
[tex]M \equiv 0 \pmod{3^2*223} \equiv 0 \pmod{2007}[/tex]

sliten og trøtt

Det skal ikke så mye til for å få dette til å fungere. Du har vist at tallet
$10^{222}-1\equiv 0\mod{223}$ slik at også $10^{222k}-1\equiv 0\mod{223}$.
Da gjenstår det å finne en passende verdi av $k$ slik at
\[\frac{10^{222k}-1}9\equiv 0 \mod{9}.\]
samtidig som $222k\leq 2007$. Observer nå at tverrsummen til
$(10^n-1)/9=11...1$ er $n$. Dermed, siden et tall er kongruent
med sin tverrsum modulo $9$, holder det å velge $k$ slik at $9$
deler $222k$. Følgelig vil $k$ lik $3$, $6$ eller $9$ fungere.

Løste den litt annerledes: hvis ett av tallene i mengden er delelige med $2007$, er vi ferdige. Hvis ikke, vil minst to forskjellige tall ha samme rest delt på $2007$. $2007$ deler da deres differanse $11...1\cdot 10^k$, og siden $(2007,10)=1$, er vi ferdige.

OK, kan denne løses ved " pigeonhole principle" av to tall?
Noen?

stensrud wrote:Løste den litt annerledes: hvis ett av tallene i mengden er delelige med $2007$, er vi ferdige. Hvis ikke, vil minst to forskjellige tall ha samme rest delt på $2007$. $2007$ deler da deres differanse $11...1\cdot 10^k$, og siden $(2007,10)=1$, er vi ferdige.

Forresten, er dette " pigeonhole principle" ?

Janhaa wrote: Forresten, er dette " pigeonhole principle" ?

Stemmer, glemte å nevne det.