Vi har en oppgave angående deling.
Vi har et uttrykk gitt ved
[tex]P((x,n))= n^x-n [/tex]
Vi skal finne ut om
[tex]P((x,k+1)-P((x,k))[/tex] [symbol:identisk][tex]0(mod x)[/tex]
Dette er også
[tex](k+1)^x-k^x-1[/tex] [symbol:identisk] [tex]0(mod x)[/tex]
Og koefisientene korrosponderer med Pascals trekant hvis man fjerner enerene.
Det er helt klart at dette er sant når x er et primtall, og det er ikke sant når det ikke er et primtall. Jeg har allerede bevist at det er sant når det er et primtall ved å vise at alle ledd er delelige. Det kommer av at når det er et primtall vil alle ledd se slik ut [tex]x!/(a!b!)[/tex] hvor [tex]a+b=x[/tex] [tex]a,b>0[/tex] og siden x er et primtall vil [tex]gcd((a!b!),x)=1[/tex], og siden [tex]gcd((a!b!),x)=1[/tex] vil det bety at man kan dele på x i alle ledd.
Vet noen av dere hvordan man beviser det motsatte? Jeg klarer ikke å finne en god metode for det.
Bevis angående deling
Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Du har nok egentlig klart det allerede: Hvis du skal motbevise noe, i dette tilfellet at påstanden ikke stemmer for x uprim, holder det å finne et moteksempel.
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Hvis du skulle bevise det, stemmer det som du sier at et moteksempel ikke er nok, men aldri stemmer blir vel litt å ta i her: Hvis x=1 stemmer det alltid og hvis for eksempel x=4 og k=2 stemmer påstanden også.
Ja, men nå er k alle verdier og for et eller annet tall vil det ikke stemme for x=4. Det er det jeg prøver å bevise, at når x er ikke et primtall vil en verdi av k føre til atmrcreosote skrev:Hvis du skulle bevise det, stemmer det som du sier at et moteksempel ikke er nok, men aldri stemmer blir vel litt å ta i her: Hvis x=1 stemmer det alltid og hvis for eksempel x=4 og k=2 stemmer påstanden også.
[tex]P((x,k+1)-P((x,k))[/tex] [symbol:identisk][tex]0(mod x)[/tex] ikke er sant.
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Er du sikker på dette holder?
Jeg får uttrykket til å bli [tex]S=(k+1)^x-k^x-1[/tex]. Hvis x er like, kan du bare velge k=x-1 som gjør at [tex]S\equiv-2\ne0[/tex] siden x er sammensatt.
Hvis derimot x er ulike, risikerer du trøbbel, første gang for x=561: [tex](k+1)^{561}-k^{561}-1\equiv0[/tex] for alle hele k.
Jeg får uttrykket til å bli [tex]S=(k+1)^x-k^x-1[/tex]. Hvis x er like, kan du bare velge k=x-1 som gjør at [tex]S\equiv-2\ne0[/tex] siden x er sammensatt.
Hvis derimot x er ulike, risikerer du trøbbel, første gang for x=561: [tex](k+1)^{561}-k^{561}-1\equiv0[/tex] for alle hele k.
Vet ikke helt hva du mener med like og ulike?
Virkelig, er dette sant at hvis du deler [tex]S=(k+1)^{561}-k^{561}-1[/tex] med 561 vil du aldri få noe rest. Veldig interesant, men hvordan kom du frem til det fordi jeg må faktisk vise at dette er sant og gå gjennom alle de 560 leddene blir litt for mye jobb. Jeg har prøvd med noen tall, og det ser ut som at du har rett.
Ikke glem at jeg bare går i andre klasse på videregående og kan ikke alt for mye moduloregning.
Virkelig, er dette sant at hvis du deler [tex]S=(k+1)^{561}-k^{561}-1[/tex] med 561 vil du aldri få noe rest. Veldig interesant, men hvordan kom du frem til det fordi jeg må faktisk vise at dette er sant og gå gjennom alle de 560 leddene blir litt for mye jobb. Jeg har prøvd med noen tall, og det ser ut som at du har rett.
Ikke glem at jeg bare går i andre klasse på videregående og kan ikke alt for mye moduloregning.
Du trenger ikke noen resultater fra moduloregning i det hele tatt egentlig.
Det eneste du egentlig trenger oversikten over er, dersom du skulle gange ut parantesen, hvor mange ledd vil ha en potens av [tex]k[/tex], og dermed også være delelig med [tex]k[/tex], og hva blir konstantleddet?
Det eneste du egentlig trenger oversikten over er, dersom du skulle gange ut parantesen, hvor mange ledd vil ha en potens av [tex]k[/tex], og dermed også være delelig med [tex]k[/tex], og hva blir konstantleddet?
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Like tall er partall, ulike odde.
Det kan virke hardt å sjekke alle 561 muligheter, men heldigvis fins det noen snarveier: Vi har primtallsfaktoriseringa 561=3*11*17, så det holder å vise at S er kongruent med 0 modulo 3, 11, 17 for alle hele k.
Jeg kan gjøre det modulo 11: Hvis k er 0 eller -1, holder det opplagt, anta derfor at k ikke er en av disse. Fermats lille teorem gir så at [tex]a^{10}\equiv1[/tex], følgelig er [tex]a^{561}=a\cdot (a^{10})^{56}\equiv a\cdot1^{56} = a[/tex], så vi har [tex]S=(k+1)^{561}-k^{561}-1\equiv (k+1)-k-1=0[/tex]. Du kan vise det tilsvarende for 3, 17.
Sjølkorrigering: Jeg kan ikke garantere at x=561 er første gangen det feiler. Men det vil feile for alle Carmichael-tall, og disse fins det faktisk uendelig mange av.
Er dette forresten ei oppgave du har funnet på sjøl, eller sto den i en lærebok?
Cauchy: Hvordan vil du gjennomføre dette i praksis? Allerede koeffisienten til k^558 vil være en brøk (ha 3 i nevner) når du ekspanderer ((k+1)^561)/561, og dette vil nok gjøre seg gjeldende i en del andre ledd også slik at det blir håpløst å følge med på. Metoden fungerer for primeksponenter, men usikker på om det går bra her?
Det kan virke hardt å sjekke alle 561 muligheter, men heldigvis fins det noen snarveier: Vi har primtallsfaktoriseringa 561=3*11*17, så det holder å vise at S er kongruent med 0 modulo 3, 11, 17 for alle hele k.
Jeg kan gjøre det modulo 11: Hvis k er 0 eller -1, holder det opplagt, anta derfor at k ikke er en av disse. Fermats lille teorem gir så at [tex]a^{10}\equiv1[/tex], følgelig er [tex]a^{561}=a\cdot (a^{10})^{56}\equiv a\cdot1^{56} = a[/tex], så vi har [tex]S=(k+1)^{561}-k^{561}-1\equiv (k+1)-k-1=0[/tex]. Du kan vise det tilsvarende for 3, 17.
Sjølkorrigering: Jeg kan ikke garantere at x=561 er første gangen det feiler. Men det vil feile for alle Carmichael-tall, og disse fins det faktisk uendelig mange av.
Er dette forresten ei oppgave du har funnet på sjøl, eller sto den i en lærebok?
Cauchy: Hvordan vil du gjennomføre dette i praksis? Allerede koeffisienten til k^558 vil være en brøk (ha 3 i nevner) når du ekspanderer ((k+1)^561)/561, og dette vil nok gjøre seg gjeldende i en del andre ledd også slik at det blir håpløst å følge med på. Metoden fungerer for primeksponenter, men usikker på om det går bra her?
Jeg forsto forklaringen din f.eks.mrcreosote skrev:Like tall er partall, ulike odde.
Det kan virke hardt å sjekke alle 561 muligheter, men heldigvis fins det noen snarveier: Vi har primtallsfaktoriseringa 561=3*11*17, så det holder å vise at S er kongruent med 0 modulo 3, 11, 17 for alle hele k.
Jeg kan gjøre det modulo 11: Hvis k er 0 eller -1, holder det opplagt, anta derfor at k ikke er en av disse. Fermats lille teorem gir så at [tex]a^{10}\equiv1[/tex], følgelig er [tex]a^{561}=a\cdot (a^{10})^{56}\equiv a\cdot1^{56} = a[/tex], så vi har [tex]S=(k+1)^{561}-k^{561}-1\equiv (k+1)-k-1=0[/tex]. Du kan vise det tilsvarende for 3, 17.
Sjølkorrigering: Jeg kan ikke garantere at x=561 er første gangen det feiler. Men det vil feile for alle Carmichael-tall, og disse fins det faktisk uendelig mange av.
Er dette forresten ei oppgave du har funnet på sjøl, eller sto den i en lærebok?
Cauchy: Hvordan vil du gjennomføre dette i praksis? Allerede koeffisienten til k^558 vil være en brøk (ha 3 i nevner) når du ekspanderer ((k+1)^561)/561, og dette vil nok gjøre seg gjeldende i en del andre ledd også slik at det blir håpløst å følge med på. Metoden fungerer for primeksponenter, men usikker på om det går bra her?
[tex](k+1)((k+1)^{230})^2-(k)((k)^{230})^2-1[/tex] [symbol:identisk] [tex]k+1-k-1=0 (mod 561)[/tex]
Problemet er at når jeg skjekker dette ut i praksis er jeg ikke like heldig. Ihvertfall, ikke hvis jeg gjør det på måten som læreren gjør det på. F.eks. 561C3 som ikke er delelig på 561. Dette går jo rett mot det vi beviste og jeg tror dermed at enten har vi utført beviset feil eller så kommer det av at det ikke bare er 561C3 som trenger å være delelig, men det er hele uttrykket som trenger eå være delig og jeg har ikke sett noen unntak til det.
Uansett, dette er en skoleoppgave og det er ganske viktig at jeg får det til fordi jeg får karakter på det.
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Jeg er ikke helt med på andre avsnitt, veit ikke åssen læreren din har gjort det. Hva er egentlig oppgava du har fått?
Forståelig, jeg formulerte meg litt dårlig.mrcreosote skrev:Jeg er ikke helt med på andre avsnitt, veit ikke åssen læreren din har gjort det. Hva er egentlig oppgava du har fått?
Læreren min er ikke spesiellt flink fordi han er norsk (Han er bedre enn de fleste norske lærerene, men har betydlige hull), men pensum er tøft. Når vi beviste at S er delelig på alle primtall viste vi det ved å vise at alle ledd er delelig med x.
Han tenkte at det også gikk motsatte veien at hvis et av leddene ikke er delelig med x ville S ikke være delelig med x, men det er ikke sant fordi f.eks. [tex]3+3+6+8=20[/tex] her er [tex]20[/tex][symbol:identisk] [tex]0(mod2)[/tex], men [tex]3[/tex][symbol:identisk] [tex]1(mod2)[/tex]
Hver gang jeg går gjennom det du har skrevet blir jeg mer og mer sikker på at det du skriver er sant. I tilegg når dere er enda mer sikker enn meg så er jeg ganske sikker på at dette er det man bør gjøre.
Det er ikke en vanlig oppgave som man finner i en skrivebok. Jeg skriver en mattestil og den er allerede på 6 sider. Den er ferdig nå etter at jeg inkluderte det dere fortalte meg her.
Uansett, tusen takk for all hjelpen.
Hvis det er noen som lurer på hva oppgavene er, her er de
1. Factorize the expression [tex]P(n)=n^x-n[/tex] for[tex] x = 2,3,4,5[/tex]. Determine if the expression is always divisible by the corresponding x. If divisible use mathematical induction to prove your result by showing whether [tex]P(k+1)-P(k)[/tex] is always divisible by x. Using appropriate technology, explore more cases and make a conjecture for when [tex]n^x - n[/tex] is divisible by x.
2. Explain how to obtain the entries in Pascal's triangle...State the relationship between the expression [tex]P(k+1)-P(k)[/tex] and Pascal's traingle. Reconsider your conjecture.
Write an expression for the xth row of the Pascal's Triangle. You will have noticed that (x C r) = k, k is a natural number. Determine when k is a multiple of x.
3. Make conclusions regarding the last result in part 2 and the form of proof by inductiton used in this assignment. Refine your conjecture if neccessary, and prove it.
4. State the converse of your conjecture. Describe how you woul prove whether or not the converse holds.
1. Factorize the expression [tex]P(n)=n^x-n[/tex] for[tex] x = 2,3,4,5[/tex]. Determine if the expression is always divisible by the corresponding x. If divisible use mathematical induction to prove your result by showing whether [tex]P(k+1)-P(k)[/tex] is always divisible by x. Using appropriate technology, explore more cases and make a conjecture for when [tex]n^x - n[/tex] is divisible by x.
2. Explain how to obtain the entries in Pascal's triangle...State the relationship between the expression [tex]P(k+1)-P(k)[/tex] and Pascal's traingle. Reconsider your conjecture.
Write an expression for the xth row of the Pascal's Triangle. You will have noticed that (x C r) = k, k is a natural number. Determine when k is a multiple of x.
3. Make conclusions regarding the last result in part 2 and the form of proof by inductiton used in this assignment. Refine your conjecture if neccessary, and prove it.
4. State the converse of your conjecture. Describe how you woul prove whether or not the converse holds.