Springen naar inhoud

bewijs


  • Log in om te kunnen reageren

#1

Nabuko Donosor

    Nabuko Donosor


  • >25 berichten
  • 94 berichten
  • Ervaren gebruiker

Geplaatst op 12 januari 2006 - 19:03

Stelling
Stel n een natuurlijk getal en p priem. Als q een positieve deler is van (n+1)^p-n^p dan is p een deler van q-1.
Bewijs
??

Ik heb het al, ik wil gewoon eens zien of er geen betere manier is.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 12 januari 2006 - 20:59

Wist je dat... die vraag door BelgiŽ ingediend werd voor de Baltic Way competitie in Zweden dit jaar, dat de vraag geselecteerd werd en dat ik er de auteur van ben? :P Hehe. Leuk dat hij hier terechtkomt. (Baltic Way is een internationale wiskundige teamcompetitie en BelgiŽ was daar dit jaar te gast. Elk land dat deelneemt moest ook vragen meebrengen voor de competitie, en de Belgische vragen werden door mij opgesteld. Dit was de 16de vraag van de competitie, de eerste van de 20 was ook van mijn hand.)

Geef jij jouw oplossing eens, Nabuko Donosor? :roll:

#3

*_gast_PeterPan_*

  • Gast

Geplaatst op 13 januari 2006 - 10:53

Knap probleem Ernie!

Gegeven is:
(n+1)p = np (mod q)
{Ik gebruik het =teken omdat ik geen equivalentieteken heb}

Hieruit blijkt al direkt dat q geen deler kan zijn van n of n+1.
Volgens de kleine stelling van Fermat is dan
1 = (n+1)q-1 = nq-1 (mod q)

Stel nu dat p geen deler is q-1, dan is ggd(p,q-1)=1 en dus zijn er natuurlijke getallen r en s zo dat
1 = p.r - (q-1).s of 1 = (q-1)s - pr.
Bekijk het geval (q-1)s = pr + 1. (Het andere geval gaat op dezelfde manier).
Dan is n.npr= npr+1 = n(q-1)s = (n+1)(q-1)s = (n+1)pr+1 = (n+1).(n+1)pr = (n+1).npr (mod q)
Dus is n = n+1 (mod q)
Dat is onjuist, dus p is een deler van q-1.

#4

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 13 januari 2006 - 11:50

Hmz, je bent eigenlijk vergeten te vermelden dat je dat bewijst voor alle *priem*delers q en dat daaruit het resultaat voor *alle* delers volgt.

De oplossing die ik oorspronkelijk had maakt gebruik van een lichtjes obscuur lemma (niet zo bekend, maar ja), dat zegt: als a en b onderling ondeelbare natuurlijke getallen zijn dan geldt er voor alle natuurlijke getallen m en n dat (a^m - b^m, a^n - b^n) = a^(m, n) - b^(m, n). [Hierbij bedoel ik met (m, n) dus de grootste gemene deler van m en n.] En met dat lemma is het niet zo moeilijk: zij q een priemdeler van (n + 1)^p - n^p. Dan zijn (n + 1)^p - n^p en (n + 1)^(q - 1) - n^(q - 1) zeker deelbaar door q (op een paar uitzonderingsgevallen na, maar in die gevallen is het vrij duidelijk dat het toch niet kan kloppen). Dus is ook (n + 1)^(p, q - 1) - n^(p, q - 1) deelbaar door q, dus kan er niet gelden dat (p, q - 1) = 1. Bijgevolg moet p een deler zijn van q - 1...

Dat is echter niet de oplossing die ik uiteindelijk ingediend heb als "officiŽle oplossing" omdat die dus, zoalsik zei, met een vrij onbekend lemma werkt. Voor de officiŽle oplossing heb ik met inversen en ordes gewerkt, dat was iets meer werk, maar toch nog steeds goed te doen.

De vraag werd wel niet goed opgelost tijdens de competitie. Slechts 3 van de deelnemende landenteams vonden de oplossing: Duitsland, Rusland en Polen.

#5

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 13 januari 2006 - 11:54

En ik geef ook direct de andere vraag die geselecteerd werd:

Definieer de rij van natuurlijke getallen a[0], a[1], ..., a[2005] als volgt: als a[n] = c_1c_2...c_k de decimale schrijfwijze van a[n] is (de getallen c[j] zijn dus de "cijfers" waaruit a[n] is opgebouwd) dan is a[n + 1] = c_1^2005 + c_2^2005 + ... + c_k^2005. Bestaat er een waarde van a[0]zodat alle termen van deze rij verschillend zijn?

Dit vond ik persoonlijk een vrij zwakke en makkelijke vraag (zeker niet zo goed als de andere 5 die ik instuurde) maar hij werd toch geselecteerd... vreemd... Spijtig genoeg kan ik de 4 niet-geselecteerde vragen niet posten omdat die mss wel eens in de finaleronde van een of andere olympiade zouden kunnen komen :wink:

#6

*_gast_PeterPan_*

  • Gast

Geplaatst op 13 januari 2006 - 18:33

Hmz, je bent eigenlijk vergeten te vermelden dat je dat bewijst voor alle *priem*delers q en dat daaruit het resultaat voor *alle* delers volgt.

Daar heb je helemaal gelijk in. In de 'gauwigheid' vergeten. :roll:

Dat tweede probleem vond die commissie natuurlijk interessant vanwege het voorkomen van het getal 2005. Heeft iemand al een oplossing?

#7

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 13 januari 2006 - 19:34

Sorry, ik schreef per ongeluk "de rij a[0], a[1], ..., a[2005]" maar ik bedoelde "de oneindige rij a[0], a[1], ..." :roll:

#8

*_gast_PeterPan_*

  • Gast

Geplaatst op 13 januari 2006 - 22:23

Ik heb een antwoord op dit probleem, maar ik wacht nog in de hoop dat iemand anders met een antwoord komt.
Ik vond dit probleem iets lastiger dan het vorige. Hoeveel deelnemers hadden een goede verklaring gevonden?

#9

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 13 januari 2006 - 22:56

Ongeveer de helft van de deelnemende teams loste die vraag correct op.

De andere vraag (die over n, p en q) werd dus als moeilijker ervaren. :roll:

#10

*_gast_PeterPan_*

  • Gast

Geplaatst op 14 januari 2006 - 22:00

limn->~92005n/10n-1 = 0,
dus is er een N zo dat 92005n < 10n-1 voor alle n :D N.
Stel we kiezen zo'n N.

Zij n :) :? en a[n] bestaat uit m cijfers met m :P N.
Dan is a[n] :P 10m-1 en
a[n+1] :roll: m.92005 (want de m cijfers zijn allen :P 9).
Dan is a[n+1] :D m.92005 < 10m-1 :) a[n].
Kortom, als a[n] uit minstens N cijfers bestaat zal a[n+1] < a[n] zijn.

Conclusie: Als a[1] uit minstens N cijfers bestaat, dan zal het rijtje a[1], a[2], a[3], ...
aanvangs dalen tot (zeg) a[k], waarbij a[k] maximaal N cijfers bevat.
Bewering: a[n] bevat maximaal N cijfers voor n :P k.
Met volledige inductie.
Het is waar voor a[n] met n = k.
Stel dat r :P k en a[r] maximaal N cijfers bevat. Dan is
a[r+1] :? N.92005 < 10N-1 en bevat dus maximaal N cijfers.

Dus a[n] kan slechts eindig veel waarden aannemen (maximaal k + 10N-1) en dus zullen alle a[i]'s niet ongelijk aan elkaar kunnen zijn.

#11

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 14 januari 2006 - 22:19

Ja, daar komt het op neer :roll: Beetje een flauwe vraag hť...

#12

*_gast_PeterPan_*

  • Gast

Geplaatst op 15 januari 2006 - 10:19

Het goed opschrijven maakt het probleem lastig.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures