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.
Litt tallteori
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Dolandyret
- Lagrange
- Innlegg: 1264
- Registrert: 04/10-2015 22:21
"I want to die peacefully in my sleep like my grandfather, not screaming in terror like his passengers."
Prøver meg:Dolandyret skrev: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.
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
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
-
Brahmagupta
- Guru
- Innlegg: 628
- Registrert: 06/08-2011 01:56
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.
$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.
Forresten, er dette " pigeonhole principle" ?stensrud skrev: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.
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]