Matematické Fórum

bobik · 06. 11. 2008 17:08 — Editoval bobik (06. 11. 2008 17:18)

Ahojte, mám takýto problém. Mám dokáza?, že
$343 | 2^{147} - 1$

Skúšal som už všeličo hlavne v oblasti kongruencií. Ak to mám preformulova? pýtam sa či

$2^{147} \equiv 1 (mod 343)$

Začal som hlavne tým, že som si 343 rozložil na prvočíselný rozklad 343 = 7*7*7 a toto som spravil aj s mocninou dvojky 147 = 3*7*7,
Viem dokáza?, že platí
$2^{147} \equiv 1 (mod 7)$ ,
ale z tohto sa neviem dosta? k modulu 343.
Chcel som to skúsi? rieši? pomocou tranzitívnosti kongruencií, ale zamotal som sa v tom.
Problém mi robí hlavne to, že rozkladom 343 je 7*7*7 čo sú tri súdeliteľné čísla a pri kongruenciách si s tým neviem da? rady, popri tom neviem ako inak to rieši? ako cez kongruencie.

Neviem si da? s tým radi, poraďte prosím.

ďakujem bobik

Kondr · 06. 11. 2008 18:26

Je možné použít postupné umocňování: 147=128+16+2+1, takže pokud budu znát 2^128 a 2^16 podle modulu 343, mám vyhráno. A počítat postupně 2, 2^2, 2^4, 2^8, 2^16,... je poměrně rychlé.

Myslím ale, že toto je příklad na Eulerovu větu: pokud a je nesoudělné s n, pak $n|a^{\phi{n}}-1$ . n=343 a a=2 jsou nesoudělné, větu lze použít. Odtud máme, že $343|2^{294}-1$ , $343|(2^{147}-1)(2^{147}+1)$ .
Číslo 343 dělí jednu ze závorek, s druhou je nesoudělné. Jak jsi ale ukázal, 7 dělí první z nich, takže máš vyhráno.

bobik · 06. 11. 2008 18:48

↑ Kondr:
Pár vecí mi tam nie je jasných tak sa radšej opýtam.
viem, že eulerova funkcia je počet kladných celých čísel nesúdeliteľných s kladným číslom n, menších alebo rovných n, ale ako si prišiel k číslu 294 , či pracne?
A ešte jedna vec ak $7 | 2^{147}-1$ tak potom aj 343 delí toto číslo? lebo mi nie je jasné ktorú zátvorku to myslíš.

ďakujem

lukaszh · 06. 11. 2008 20:08

↑ Kondr:
Zdravím, chcel by som sa opýta? či tento postup je korektný (mám medzery s modulom a dos? ho nechápem):
Mám dokáza?, že $7|2^{21}-1$
Postupujem takto:
$2^{21}\equiv1\;\pmod{7}$
Rozpíšem číslo 2^21:
$$2^{3}$^7\equiv1\;\pmod{7}$
Viem, že 2^3 dáva zvyšok 1 po delení siedmimi:
$1^7\equiv1\;\pmod{7}$
Pôvodný výrok je teda pravdivý.
Je to správne alebo zle?

dr.dracek

↑ lukaszh:

to neplatí lukaszhi protože podle fermatovy věty je to jinak trochu
http://cs.wikipedia.org/wiki/Mal%C3%A1_ … _v%C4%9Bta
, ale taky nemůžu přijít na kloub tohoto příkladu apodle mě ↑ Kondr: s kondrem nesouhlasím až na to příjdu, tak to sem napíšu

lukaszh · 06. 11. 2008 20:33

↑ dr.dracek:
A ako to teda mám dokazova??

Pavel Brožek

↑ bobik:

Myslím, že to Kondr myslel tak, že pokud 7 dělí $2^{147}-1$ , pak nutně 7 nedělí $2^{147}+1$ (je to číslo pouze o dvě větší než číslo dělitelné 7). Proto pokud $343|(2^{147}-1)(2^{147}+1)$ , tak všechny ty sedmičky z 343=7*7*7 musí být v $2^{147}-1$

↑ dr.dracek:

Já nevidím, že by ↑ lukaszh: používal Fermatovu větu (používá ekvivalentní úpravy a přejde k něčemu, co je zřejmě pravda) a i kdyby ji použil na $$2^{3}$^7\equiv2^3\;\pmod{7}$ , tak to vyjde stejně.

Kondr · 06. 11. 2008 21:13

↑ BrozekP: Přesně tak jsem to myslel. Všechny sedmičky musí být ve stejné závorce a když je jedna v té první, jsou tam všecky tři. Omlouvám se, pokud to z prvního příspěvku nebylo zřejmé.

bobik · 06. 11. 2008 22:10 — Editoval bobik (06. 11. 2008 22:36)

uz som to hádam pochopil, ďakujem vám veľmi pekne hlavne Kondr-ovi a BrozekP-ovi

↑ dr.dracek: pochybuje o tomto riešení, tak ho skúsim presvedči? tým, že to celé zhrniem.

Vieme, že D(343,2)=1 a na základe toho môžeme uvažova? o Eulerovej vete
$n|a^{\phi(n)}-1$ v tomto konkrétnom prípade by to bolo $343 | 2^{\phi(343)}-1$ , kde
$\phi(343)$ určíme pomocou vz?ahu $\prod_{1}^{1}(7^3 - 7^2)=294$ , pretože $343 = 7^3$ , potom po dosadení do Eulerovej vety platí

$343|2^{294}-1$ čo môžeme prepísa? do tvaru $343|(2^{147}-1) (2^{147}+1)$

Ďalej vieme dokáza?, že $7 | 2^{147}-1$ a to tak, že
$2^{3}\equiv 1 (mod 7)$ potom
$(2^{3})^{49}\equiv 1^{49} (mod 7)$ a potom dostávame
$2^{147}\equiv 1 (mod 7)$

ak ale $7 | 2^{147}-1$ , tak potom musí nutne plati? (pretože 7 nemôže delit $2^{147}+1$ & 343=7*7*7), že $343|(2^{147}-1)$

čím je dôkaz hotový

janushka · 21. 11. 2008 21:49

caute..

ja mam taky problem s jednou ulohou..
a to mame najst 2009 - ciferne cislo, ktore ma vo svojom zapise (klasicky napisane proste) len cislice 2 a 9; a je delitelne cislom 2^2009..a teda sa nas pytaju ci take cislo existuje..a ked tak kolko ich je?

noo a mam taky pocit, ze by to mohlo nejak ist cez kongruencie..ale vobec neviem ako..mohli by ste mi niekto poradit...o:-) dakujeeeem..:)

Kondr · 22. 11. 2008 00:10

↑ janushka:Tohle se dokazuje indukcí: dokaž, že existuje n-ciferné číslo složené jen z cifer 2 a 9 dělitelné 2^n. To je celkem lehké a kýžený výsledek je pak zvláštním případem.

Matematické Fórum

#1 06. 11. 2008 17:08 — Editoval bobik (06. 11. 2008 17:18)

Kongruencie alebo operácia delenia

#2 06. 11. 2008 18:26

Re: Kongruencie alebo operácia delenia

#3 06. 11. 2008 18:48

Re: Kongruencie alebo operácia delenia

#4 06. 11. 2008 20:08

Re: Kongruencie alebo operácia delenia

#5 06. 11. 2008 20:31 — Editoval dr.dracek (06. 11. 2008 20:38)

Re: Kongruencie alebo operácia delenia

#6 06. 11. 2008 20:33

Re: Kongruencie alebo operácia delenia

#7 06. 11. 2008 21:06 — Editoval BrozekP (06. 11. 2008 21:07)

Re: Kongruencie alebo operácia delenia

#8 06. 11. 2008 21:13

Re: Kongruencie alebo operácia delenia

#9 06. 11. 2008 22:10 — Editoval bobik (06. 11. 2008 22:36)

Re: Kongruencie alebo operácia delenia

#10 21. 11. 2008 21:49

Re: Kongruencie alebo operácia delenia

#11 22. 11. 2008 00:10

Re: Kongruencie alebo operácia delenia

Zápatí