Matematică simplă?

Question

n fiind un număr natural, oricare, mai mare decît 1, este posibil să existe acest n care să dividă (2^n) -1 sau nu ?

Comments

Nu cred că folosește la ceva comentariul meu, dar poftim. Am încercat numeric și am găsit că pînă pe la n = 50 nu există nici un astfel de număr. Precizia obișnuită de calcul digital mă împiedică să merg mai departe de 50. Probabil aș putea merge mai departe pe căi neconvenționale, dar bănuiesc că doriți o demonstrație analitică.

---

Am rîs cu lacrimi la verificarea făcută de dvs. Sper că aţi făcut fuguţa un program minuscul pe care l-aţi folosit pentru acest lucru şi puteţi să-l lăsaţi să socotească în continuare, poate va găsi o soluţie sau nu? Mulţumesc pentru efortul depus. După ce voi termina de bătut (la cap) nişte conţopişti care nu ştiu de unde tot apar şi se tot multiplică, poate vin cu o soluţie competitivă la această problemă frumoasă de matematică.

---

Nu e chestie de timp de calcul, ci de cîte cifre pot avea numerele care intervin. 2^50 e aproape de limita de precizie a programelor de calcul obișnuite. Mai departe rotunjirile care se fac sînt mai mari decît 1, deci nu mai pot vedea dacă împărțirea e cu rest sau nu. Asta în MATLAB; probabil în alte programe se mai poate merge un pic, poate pînă la 2^64. Cu programe dedicate, indiferent de limbaj, se poate merge bineînțeles mult mai departe. Aș putea face asta, dar nu cred că merită efortul (pentru mine).

Rostul verificării a fost să văd dacă nu găsesc o soluție între primele valori ale lui n, pentru că dacă găseam problema era rezolvată în 5 minute cu efort practic nul.

---

Deci dacă aţi fi găsit o soluţie cu ajutorul computerului, vă duceaţi mulţumit la masă, rezultatul contează şi nu modalitatea de a-l obţine.

---

Da, sigur. Dacă găseam o soluție atunci problema existenței a cel puțin unei soluții era rezolvată. Pentru că asta se cere, existența. Poate nu știți, dar așa se face matematica azi. Calculatorul se folosește intens pentru astfel de verificări simple, care pe hîrtie ar dura o veșnicie.

Doar n-o să-mi spuneți că n-ați încercat și dumneavoastră divizibilitatea măcar pentru primele două-trei valori ale lui n. De altfel enunțul problemei sugerează el însuși că cineva a făcut o verificare, pentru că l-a exclus pe n = 1.

Ei, eu am încercat divizibilitatea pentru primele cîteva zeci de numere, fără să-mi transpire creierul. (Progrămelul are 4 linii, din care numai una face calcule și restul fac ciclarea.) Și nu cred că ar trebui să-mi fie așa rușine pentru asta încît să nu pot mînca liniștit. Dimpotrivă, cred că am făcut un lucru bun încercînd. De data asta n-a mers, asta e. Dar data viitoare voi încerca din nou. Cele 5 minute mă pot scuti de o întreagă bătaie de cap. Și o spun din experiență, pentru că mi s-a întîmplat de nenumărate ori.

Bănuiesc că unii au ridicat din sprîncene și atunci cînd matematicienii au început să folosească creionul și hîrtia, plîngînd după vremea cînd totul se făcea mintal sau cu bățul în nisip.

Mais où sont les neiges d'antan?

---

Mais il ya au moins dans notre imagination, competences des ancestres.

Nu doream probarea existenţei sau inexistenţei unei soluţii, ci  o rezolvare  matematică  a problemei.

---

Problema cere verificarea existenței. Nu are importanță dacă o găsim căutînd-o bob cu bob sau făcînd calcule cu formule. În schimb e drept că inexistența poate fi dovedită numai cu formule, pentru că nimeni (și nici un calculator) nu poate lua la mînă toate n-urile posibile ca să verifice divizibilitatea.

---

Întrebarea într-adevăr cere numai dacă există un n, dar cum bine v-aţi dat seama nu doresc calcul mecanic. Bineînţeles că am făcut şi eu nişte încercări de test cu primele numere naturale, fapt ce m-a condus la ideea că inducţia matematică se poate folosi, eventual îmbinată cu reducerea la absurd.

---

Eu am observat ca deimpartitul (2^n)-1 fiind impar, catul c si impartitorul n, trebuie obligatoriu sa fie ambele impare. Ce este imprecis aici?. Luand pe n=cu 3; 5; 7; si 9, pe hartie, am observat ca restul era tot timpul un multipu al lui 2, la fel si partea intreaga a catului, suficient cat sa realizez ca si la n mai mare se va intampla exact la fel. Am dedus astfel ca impartirea exacta este imposibila cu exceptia solutiei/situatiei excluse de enuntul care cere ca n sa fie mai mare decat 1. Singura solutie ar putea fi cea in care n ar putea fi egal cu 1. Raspuns final: NU ESTE POSIBIL!

---

 Afirmaţia dvs. "suficient cat sa realizez ca si la n mai mare se va intampla exact la fel." nu este o demonstraţie matematică. Imprecizia la care m-am referit s-ar putea transforma cu un mic efort în precizie. 

Answer 1

Soluția mea folosește mica Teoremă a lui Fermat (demonstrată de Leibniz și Euler) care spune că, dacă două numere naturale a și p sunt prime între ele iar p este prim atunci p divide expresia a^(p-1) - 1.

În cazul nostru a=2 iar n trebuie să fie, evident, impar, deci 2 și n sunt prime între ele.

Pentru cazul în care n e prim avem, din relația lui Fermat, pentru a=2 și p=n

n divide 2^(n-1)-1 sau, inmulțind expresia cu 2, n divide (2^n) - 2. 

Asta înseamnă că n nu poate divide (2^n)-1 deoarece, în numere naturale, se demonstrează simplu că dacă m divide k atunci m nu divide k+1.

 

Dacă n e neprim atunci îl descompunem în fatorii primi a și b, n = ab.

Avem:

(2^n) - 1 = (2^ab) - 1 = ((2^a)^b) - 1.   (1)

Aplicând din nou relația lui Fermat și raționând la fel ca în cazul n număr prim, scriem:

b divide ((2^a)^(b-1)) - 1 deci b divide ((2^a)^b) - 2, deci b nu divide ((2^a)^b) - 1, 

adică b nu divide (2^n) - 1.

Analog, rescriind expresia (1) sub forma (2^n) - 1 = ((2^b)^a)) - 1 se demonstrează că a nu divide (2^n) - 1.

Dacă nici a și nici b nu sunt divizori atunci nici produsul lor, n, nu divide (2^n) - 1,

deoarece, dacă un număr k se divide prin m atunci k se divide și prin divizorii lui m.

Se observă că scriind n = ab, adică descompunându-l  pe n în doi factori primi, nu se restrânge generalitatea soluției.  Având mai mulți factori primi ai lui n doar se lungește numărul pașilor similari prin care se demonstrează că niciunul din ei nu divide (2^n) - 1, deci nici produsul lor, n. 

Comments

Trebuie să recunosc că nu m-am aşteptat la o astfel de abordare, în mintea mea problema era aproape rezolvată cu totul şi cu totul altfel. Aş fi venit cu o soluţie peste un an pentru că m-am săturat să mă auto-votez, să-mi auto-răspund, ba chiar şi să-mi mulţumesc mie însămi pentru răspunsul meu. Am luat soluţia dvs. la bani mărunţi, am ajuns la concluzia nefericită pentru mine (nu doream să fie altcineva pe acest site capabil să o rezolve) că nu-mi rămîne decît să vă spun : Felicitări. Această problemă frumoasă pentru mine, ca de altfel şi alta prezentă în acest site, este o problemă de pregătire pentru Olimpiada Internaţională de Matematică.

---

Mulțumesc pentru aprecieri.

Aș fi curios să aflu și soluția dumneavoastră. Eu am încercat mai multe abordări care păreau să mă conducă la rezultatul anticipat intuitiv, dar am dat peste tot felul de dezvoltări laborioase care duceau cam nicăieri, până să sparg această nucă ce s-a dovedit destul de tare.

---

Nu mai are rost,  o voi spune vreodată la o olimpiadă, ca reper se  bazeză pe inducţie. Sînt puţin înciudată (sper că există termenul) (nu este frumos ce simt, dar trebuie să recunosc acest lucru) pentru faptul că l-aţi găsit pe amicul Fermat şi eu nu. Probabil problema se poate şi generaliza, aşa îmi sugerează chiar soluţia dvs.

Answer 2

c=[(2^n)-1]/n=[(2^n)/n]-1/n;.

deimpartitul, =(2^n)-1,  fiind impar, si n, (impartitorul), si c, (catul), trebuie sa fie impari/e, iar restul=cu 0.

2^n fiind par iar n impar, raportul lor va fi par, (partea intreaga), la fel ca si restul, (intre 2 si n-1), desi pentru indeplinirea conditiilor, si acest cat, care va fi cel final, ar trebui sa fie impar, iar restul= cu 1.

Sper ca de aceasta data n-am mai incurcat borcanele, desi nu este exclus.

Comments

(2^n) / n nu scade puterea lui 2. Probabil aţi vrut să vă distraţi.

---

Tot schimbaţi răspunsul că aproape m-aţi zăpăcit. Nu am înţeles nici ce răspuns final daţi, dar pot să spun că socotelile dvs. au un grad de imprecizie aproximat la 100%.