Teorija števil

Ko tudi učitelj ne more pomagati...
Odgovori
delta
Prispevkov: 420
Pridružen: 19.8.2009 14:16

Re: Teorija števil

Odgovor Napisal/-a delta »

Enkrat se mi zdi smo že imeli nalogo, ki je pa ne najdem. Pokaži, da je za vsako pit. trojico a^2+b^2=c^2 produkt abc deljiv s 60.
Za 4 gre, 3 in 5 pa nimam ideje. Kakšna ideja?

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Ja, to gre vse čez generatorske zveze za pitagorejske trojice. Za vsak par m>n lahko generiraš trojico
a=m^2-n^2
b=2mn
c=m^2+n^2
in od tod
abc=2mn(m^4-n^4)
Za deljivost s 5 je hitro: če je katerikoli izmed m ali n deljiv s 5, potem je delo končano. Sicer pa velja Eulerjeva formula a^4=1 mod 5 in je m^4-n^4=1-1=0 mod 5.
Za deljivost s 3 popolnoma enako: a^4=(a^2)^2=1^2=1 mod 3, če a ni deljiv s 3.

delta
Prispevkov: 420
Pridružen: 19.8.2009 14:16

Re: Teorija števil

Odgovor Napisal/-a delta »

Razumem, hvala :)

juve
Prispevkov: 20
Pridružen: 23.11.2012 19:53

Re: Teorija števil

Odgovor Napisal/-a juve »

Tudi jaz imam še nekaj vprašanj in prosim za pomoč:


1.) Dokaži da je \(p^2+2\) sestavljeno število, če je \(p\in P\) in je p različen od 3.

2.) pokaži da \(2x^2+5xy-3y^2=17\) nima celoštevilskih rešitev.... jaz sem levo stran razstavila: \(2(x-\frac{1}{2}y)(x+3y)=17\)... potem pa ne vem kako naprej..

3.) \(n^4=16p+1\) kjer je n naravno, p pa praštevilo. Poišči vse pare n,p.
Prevedla sem na kongruenco \(n^4=1 (mod 16)\) in šla reševat s polinomskimi kongruencami... dobim da tak par ne obstaja kar je malo čudno :)

4.) poišči naravno n (\(n \not=3\)), da n-3 deli n^3-3

5.) Določi n, da je rešljiva \((n+1)^2x+(n^2+1)y=1\) in za vsak tak n določi množico rešitev.
Dobim da je rešljiva za vsak naraven n in potem rešitvi \(x=\frac{n}{2}+(n^2+1)t\) in \(y=\frac{n+2}{2}-(n+1)^2t\)... je pravilno?

in še

6.)katerega leta so rojeni ljudje ki so bili leta 1997 stari toliko kolikor je vsota cifr števila, ki predstavlja letnico rojstva? (namig: reši ustrezno diofantsko enačbo)

Najlepše se zahvaljujem že vnaprej =)

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

1)
p ne more bit deljivo s 3, ker sicer ne bi bilo praštevilo. Če pa ni deljivo s 3, ima p^2 ostanek 1 po deljenju s 3, torej je p^2+2 deljivo s tri.
2)
(2x-y)(x+3y)=17
No 17 je praštevilo, tako da ga lahko razstaviš samo na dva načina: 1*17 ali 17*1. Prvi primer zahteva
2x-y=1
x+3y=17
drugi pa
2x-y=17
x+3y=1
To sta pa enostavna sistema linearnih enačb, ki jih enostavno rešiš, in ugotoviš, da rešitve niso celoštevilske.

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

3)
No n^4=1 mod 16 reši vsak lih n. Tu res potem lahko daš n=2k+1 in dobiš k*(2k^3+4k^2+3k+1)=2p in to naprej rešuješ.

Bi pa jaz raje pogledal
n^4-1=(n-1)(n+1)(n^2+1)=16p=2^4*p
p=2 in n=1 itak nista kandidata (to se ročno vidi iz prvotnega izraza), tako da lahko izključiš posebne primere.
Od tod pa takole: na levi imaš tri faktorje (vsi trije so sodi). Na desni imaš pa 5 faktorjev. Torej je vsaj eno število na levi praštevilo (saj je faktorjev premalo za 3 sestavljene), in ker so vsi trije sodi, je to praštevilo lahko samo 2! To je sigurno najmanjši faktor, torej n-1=2, n=3. Sledi p=5.

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

4)
Uf... grda :) Pomaga ti Evklidov algoritem, če n-3 deli n^3-3, potem deli tudi n^3-3-(n-3)=n^3-n=n(n-1)(n+1). Prepišiva še enkrat
n-3 deli n(n-1)(n+1)
Ena varianta je, da n-3 direktno deli enega izmed treh faktorjev.
n-3 deli n, če je n=4 ali n=6, potem pa konec, ker če je n-3>n/2, ga ne more delit
n-3 deli n-1, če je n=4 ali n=5
n-3 deli n+1, če je n=4 ali n=7
To je mogoče že dosti.

Lahko pa poiščeš vse (jih je končno število). Recimo vsi trije n, n-1 in n+1 imajo sigurno eno trojko med faktorji, tako da lahko sprobaš deljenje 3*n, 3*(n-1), 3*(n+1), in sigurno imajo en ali dva faktorja dvojke, tako da lahko še to sprobaš. Vse rešitve so
n=4, 5, 6, 7, 9, 11, 15, 27

5)
Ja to se zreducira na to, da morata biti (n+1)^2 in (n^2+1) tuji števili (in ko je to zadoščeno, morata biti x in y tudi). Na teh dveh lahko delaš Evklidov algoritem; največji skupni delitelj:
D((n+1)^2, n^2+1)=
D(n^2+2n+1, n^2+1)=
D(2n, n^2+1)=1 za vsak sod n, za lihega pa ne (saj imata člena potem skupni faktor 2). To se že iz tvojih polovičk vidi.
Potem pa tudi nekako ni prav, za t=1 tvoja rešitev ne more bit res, ker imaš same pozitivne člene, večje od 1, kar ne more pridet 1. Bo pa prav, če daš minus pred n/2 pri x.

6)
1997-(1000*x+100*y+10*z+w)=x+y+z+w
1001x+101y+11z+2w=1997
Vsi x so pozitivni in največ 9. No, seveda je x=1 (to se vidi tudi iz enačbe, ne samo iz zdrave pameti). Torej
101y+11z+2w=996
druga dva člena sta najmanj 0 in največ 117. Torej imaš dve opciji: y=8 ali y=9 zgolj iz definicijskega območja.
Če je y=9:
11z+2w=87
2w je med 0 in 18, torej je lahko z=7 ali z=6 (samo iz definicijskega območja). z mora biti seveda lih, tako da z=7 in w=5. Letnica 1975.
Če je y=8:
11z+2w=188
To zahteva z>9, torej tukaj ni rešitve.

delta
Prispevkov: 420
Pridružen: 19.8.2009 14:16

Re: Teorija števil

Odgovor Napisal/-a delta »

Kako naj pokažem, da \(n+1\) ne deli \(n!+1\)?

Uporabniški avatar
bargo
Prispevkov: 8033
Pridružen: 3.11.2004 22:41

Re: Teorija števil

Odgovor Napisal/-a bargo »

delta napisal/-a:Kako naj pokažem, da \(n+1\) ne deli \(n!+1\)?
n=2 :?:

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Joj pa ne samo n=2. Kaj pa n=4,6,10,12,16,18,...

Uporabniški avatar
bargo
Prispevkov: 8033
Pridružen: 3.11.2004 22:41

Re: Teorija števil

Odgovor Napisal/-a bargo »

:oops: Stara šola, eden zadostuje. :D

juve
Prispevkov: 20
Pridružen: 23.11.2012 19:53

Re: Teorija števil

Odgovor Napisal/-a juve »

kaj pa naslednje naloge:

1.) reši diof.enačbo \(15x-24y+14z=5\) ... preuredila sem na kongruenco modula 14 in razcepila modul na 2 in 7.... na koncu dobim da je \(x=2y+5+14t\) in pač tudi nekaj za z (ki je ravno tako odvisen od y in t), pri čemer sem y postavila za polj. parameter, t pa je pač celo število. Je to ok, ali moram dobit prav določena števila ven?
Kaj pa primer 2x+5y+100z=200??

2.) Poišči vsa naravna n, da je \(\mu (n) * \sigma (n) = -24\)
Dobim samo rešitvi n=14,15. Sem kakšno zgrešila?

3.)Poišči namanjše naravno št. n , da je \(n^2+(2n+1)^2\) popoln kvadrat... prevedem na enačbo : \((10n+4)^2-20a^2=-4\). Vzamem novi spremenljivki:
\(x=\frac{((10n+4)^2+3)(10n+4)}{2}\) in \(y=\frac{((10n+4)^2+1)a}{2}\), ki jih dobim iz izpeljave na internetu za pellovo, ki je =-4. Ko razvijem\(\sqrt{20}\), dobim da sta \((x_{0},y_{0})=(9,2)\).... vendar pa sedaj nikakor ne morem priti do nekega konkretnega n!!??

4.)\(\varphi(n)=\frac{n}{6}\), iščemo n.

5.) Iščemo VSE pit. 3 oblike \(x^2+497^2=z^2\)... dobim 2 primitivni PT (2496, 497, 2545) in (123504,497,123505)... da dobim vse pa ti dve samo pomnožim z nekim številom a?

6.) \(F(n)=\sum_{d/n}\tau(d)\) in moraš dokazat da je \(F(n^3)=1\) po modulu 3?

7.) Poišči vsa naravna št n da je \(\prod_{d/n}d=n^3\)

HVALA!

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

4) No tukaj se ozreš na izražavo \(\phi(n)=n\prod (1-1/p)\) se pravi
\(\frac16=\prod \frac{p-1}{p}\)
Razcep 6=2*3 ti pove, da imaš lahko kvečjemu 2 in 3 v imenovalcu (višji se nimajo s čim pokrajšat, saj p-1 zgoraj ni nikoli prafaktor razen za p=3). Edina možnost je torej 2/3*1/2=1/3, rešitev torej ni.

7) Načinov je dosti, najbrž sem spregledal vse enostavne :) Če n zapišeš kot produkt praštevil, recimo n=p^k*(ostalo). Delitelji so vsi možni različni produkti podmnožice teh praštevil, teh je prod(k_i+1), saj vsak delitelj lahko neodvisno izbere potenco za vsakega izmed prafaktorjev. Produkt po deliteljih lahko razbiješ rekurzivno: \(\prod_{d|n}=(\prod_{i=0}^{k_i} p_i^{k_i})^{c}\left(\prod_{c} d|({n/p_i^{k_i}})\right)^{k_i+1}\) kjer sem izfaktoriziral en prafaktor (z večkratnostjo k), s c sem pa označil število permutacij v preostalem delu števila n. To je seveda enako \(c=\prod_{j\neq i} (k_{j}+1)\). Če to poračunaš naprej, pride
\(\prod_{d|n}=(p_i^{k_i(k_i+1)/2})^{c}\left(\prod_{c} d|({n/p_i^{k_i}})\right)^{k_i+1}\)
\(=(p_i^{k_i\prod(k_i+1)/2})\left(\prod_{c} d|({n/p_i^{k_i}})\right)^{k_i+1}\)
\(=(\prod_i p_{i}^{k_i})^{(\prod (k_i+1))/2}=n^{(\prod(k_i+1))/2}\)
Preverimo smiselnost: praštevila imajo samo enega delitelja, torej je produkt deliteljev enak n, imaš pa k=1 in torej potenco 1. V redu. Kvadrat praštevila, n=p^2, ima delitelje p in p^2, torej je produkt p^3=n^(3/2). Spet ok.

Rešitev naloge je torej ta, da mora biti produkt k_i+1 za vse gradnike enak 6. Če to faktoriziraš kot 6=6, ugotoviš, da to velja za vse pete potence praštevil. Če razbiješ kot 6=3*2, je pa rešitev oblike p1*p2^2.
Prvih nekaj primerov: 12 18 20 28 32 44 45 50 52 63 68 75 76 92 98 99...

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

6) Število deliteljev je tisto, kar sva zgoraj gledala: \(\tau(d)=\prod (k_i+1)\). Zdaj moraš to spet seštet po vseh deliteljih, se pravi
\(\sum_{d|n} \prod (k_i+1)\)
Ampak ta vsota gre po deliteljih, se pravi da vsak prafaktor vidi vse svoje potence (od 0 do k). Ker so potence prafaktorjev neodvisne in se zgodijo vse kombinacije, vsakič lahko izpostaviš vse razen tistega, ki ga spreminjaš, torej lahko vsoto in produkt zamenjaš in pride:
\(\prod_{i} \sum_{j=0}^{k_i}(j+1)=\prod_i (k_i+1)(k_i+2)/2\)
Za n^3 so vsi k-ji večkratniki števila 3, od koder potem neposredno sledi, da je zgornji produkt oblike prod(1*2/2).

Joj grozno kakšna solata so tele vsote in produkti...

2) Minus pove, da je Mobiusova funkcija negativna in ima torej n liho število enojnih prafaktorjev (in vsoto deliteljev 24). Vsota deliteljev je produkt \(\prod (1+p_i)\)... razstaviš 24=2*2*2*3
Če pogledaš nekaj prvih praštevil (do 24, več nima smisla), imajo p+1=3,4,6,8,12,14,18,20,24. Pa vsakega lahko samo enkrat uporabiš. Pa liho število jih moraš uporabit. Trivialna rešitev je seveda
n=23.
Produkti treh: tukaj se pa dejansko ne da nič: preveč trojk, pa dvojka ni na razpolago.

Upam da je naloga prav razumljena...

5) Tako ja.

3) Pa saj štirko lahko izpostaviš in pokrajšaš. Od kod točno to dobiš?
No recimo da greš takoj na pitagorejske trojice in zapišeš
n=2pq
2n+1=p^2-q^2
tretja (koren desne strani) je potem p^2+q^2
(obratno ne gre, ker 2pq je sodo). Takoj lahko skombiniraš
4pq+1=p^2-q^2
1=p^2-q^2-4pq
Po modulu 4 ugotoviš, da mora bit q sodo, p pa liho. n torej deljivo s 4. No mogoče bo ta zgornja Diofantka ratala :)

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

juve napisal/-a: 1.) reši diof.enačbo \(15x-24y+14z=5\) ... preuredila sem na kongruenco modula 14 in razcepila modul na 2 in 7.... na koncu dobim da je \(x=2y+5+14t\) in pač tudi nekaj za z (ki je ravno tako odvisen od y in t), pri čemer sem y postavila za polj. parameter, t pa je pač celo število. Je to ok, ali moram dobit prav določena števila ven?
Kaj pa primer 2x+5y+100z=200??
Hm no z je treba še izrazit do konca da se preveri, jaz grem pa raje od začetka ker je težko na sredi "ujet" postopek :) Načeloma bosta 2 prosta parametra ja (očitno iz štetja prostostnih stopenj), prideta kot periodi kongruenc. Se pa da lahkotnejše module probat namesto 7. Po modulu 2 res dobiš
x=1 mod 2
Po modulu 3 je tudi odlično, saj spet dve spremenljivki izgineta:
z=1 mod 3
Iz tega že dobiš
x=1,3,5 mod 6
z=1,4 mod 6
Če bi bila samo x in z, bi bila ta oblika (vse na isti modul) že ugodna, ampak imaš še en korak, tako da kar pustiva pri miru :)
Zdaj imaš x=1+2u in z=1+3v in y se mora pa dat izrazit s tema dvema. Vstaviš
24y=15+30u + 14 + 42v - 5
24y=24+30u + 42v
To je zdaj sicer spet nesrečna nepraštevilska kongruenca (še dodatne pogoje na u in v ti lahko da - če bi pred y stal prafaktor, bi bilo enostavno, tako pa ni preveč lepo).
12y=12+15u + 21v
V glavnem to na desni mora biti z 12 deljivo, da se da y izrazit:
15u+21v=3u+9v=0 mod 12
u+3v=0 mod 4
u=v mod 4
Torej, u in v sta sinhronizirana po modulu 4. Pišeš lahko torej v=u+4w in izraziš s parametroma (u,w) vse. Polna rešitev:
x=1+2u
y=1+3u+7w
z=1+3u+12w
Zanimivo je tudi že takoj na začetku ugotovit
y=z mod 5
kar je potem iz končne rešitve seveda očitno. Ni pa treba tega. Vedno je dovolj toliko kongruenc kolikor bo prostih parametrov (idealno je, če imaš po modulu čim manj spremenljivk, tukaj se je dalo vedno dveh znebit), potem pa zadnja, da poda še dokončno zvezo med parametri, da se da zadnji parameter izrazit.

Izbira parametrov je sicer do neke mere poljubna (podobno kot realnih linearnih enačbah).

Odgovori