Deljivost sa 19

PostPoslato: Nedelja, 05. Januar 2020, 21:12
od Mile2003
Zdravo moze li pomoc oko ovog zadatka
Indukcijom dokazati da [inlmath]19[/inlmath] deli [inlmath]2^{\large2^{6n+2}}+3[/inlmath]
Meni ovde ni baza nije jasna kako da je dokazem da l stvarno ocekuju da racunam [inlmath]2^{256}+3[/inlmath] pa da delim sa [inlmath]19[/inlmath]?
Ima li neka fora ovde :D
P.S. A i preskocio sam bazu pa sam pokusao da radim ako vazi za [inlmath]n[/inlmath] da vazi za [inlmath]n+1[/inlmath] ne mogu da se ispetljam :(

Re: Deljivost sa 19

PostPoslato: Nedelja, 05. Januar 2020, 23:55
od ubavic
Tvrđenje važi u slučaju [inlmath]n=0[/inlmath], što se lako proverava, pa možeš ovaj slučaj iskoristiti za bazu indukcije.
Da bi dokazao induktivni korak, možeš iskoristiti malo modularne aritmetike. Posebno će ti biti korisna sledeća osobina: Ako je [inlmath]a\equiv b\pmod{19}[/inlmath], tada je [inlmath]a^k\equiv b^k\pmod{19}[/inlmath] za svaki prirodan broj [inlmath]k[/inlmath]. Ovo ti može pomoći i u slučaju [inlmath]n=1[/inlmath], ako baš želiš da kreneš od [inlmath]1[/inlmath].
Ovaj argument sa kongruencijom po modulu se može "raspisati" i do elementarnog nivoa, ali je ovako mnogo elegantnije.

Re: Deljivost sa 19

PostPoslato: Ponedeljak, 06. Januar 2020, 11:38
od Mile2003
Hvala na odgovoru.
Samo nije mi bas jasno je l opet idem sa onom induktivnom hipotezom pa dokazujem za [inlmath]n+1[/inlmath]?

Re: Deljivost sa 19

PostPoslato: Ponedeljak, 06. Januar 2020, 16:52
od ubavic
Da. Zašto te to buni? Da li zato što sam ti rekao da kreneš od [inlmath]0[/inlmath], ili zbog stava na koji sam te uputio (istina je da se ovaj zadatak može uraditi i bez indukcije korišćenjem samo modularne aritmetike).

Re: Deljivost sa 19

PostPoslato: Ponedeljak, 06. Januar 2020, 17:31
od Mile2003
Ja nazalost ne znam kako da razvijem ovu ideju :(
Mislim kontam da mi je
ih: [inlmath]-3\equiv2^{\large2^{6n+2}}\pmod{19}[/inlmath]
Sada dakle moram da dokazem da je [inlmath]-3\equiv2^{\large2^{6(n+1)+2}}\pmod{19}[/inlmath] dakle imacu da je [inlmath]2^{\large2^{6(n+1)+2}}=\left(2^{64}\right)^{\large2^{6n+2}}=\left(2^{\large2^{6n+2}}\right)^{64}[/inlmath] i sad po induktivnoj hipotezi vazi da je [inlmath](-3)^{64}\equiv\left(2^{\large2^{6n+2}}\right)^{64}\pmod{19}[/inlmath]
Ali [inlmath]-3\equiv3^{64}\pmod{19}[/inlmath] nije tacno

Re: Deljivost sa 19

PostPoslato: Ponedeljak, 06. Januar 2020, 18:07
od ubavic
Mile2003 je napisao:Ali [inlmath]-3\equiv3^{64}\pmod{19}[/inlmath] nije tacno

Kako nije?

Re: Deljivost sa 19

PostPoslato: Ponedeljak, 06. Januar 2020, 18:17
od Mile2003
Uf dada izvini jeste ovaj minus me zeznuo kasnije u racunu.
Hvala puno sve je jasno