Weboldalunk cookie-kat használhat, hogy megjegyezze a belépési adatokat, egyedi beállításokat, továbbá statisztikai célokra és hogy a személyes érdeklődéshez igazítsa hirdetéseit. További információ

Lineáris kongruenciák?

Figyelt kérdés

Nem tudtam ott lenni előadáson, viszont nézegettem jegyzeteket, de annyira nem értem. Szóval ezek a házik:


4x kongruens 27 mod 84

Ha minden igaz, úgy kell kezdeni, hogy megnézem a 4-nek és a 84-nek az lnko-ját, ami 4, de a 4 nem osztja a 27-et, ezért nincs megoldás. (?)


4x kongruens 27 mod 43

Itt lnko(4,43)=1, ami azt is jelenti, hogy ennyi megoldása lesz. 4x-43y=27 diofantikus egyenletet kapok, de nem tudom, hogy ez a jó út-e, illetve, ha igen, akkor mi a menete.


4x kongruens 26 mod 82

lnko(4,82)=2, 2 osztja a 26-ot, szóval lesz megoldás. Leoszthatunk 2-vel, így lesz 2x kongruens 13 mod 41, és akkor itt elvileg 41 megoldás lesz? Egyet megtaláltam, a 27-et.


Tudna valaki ebben segíteni? Köszönöm szépen.



okt. 14. 20:25
 1/4 anonim ***** válasza:
100%

1. Így van. Hogy miért lehet osztani, az gyakorlatilag azért van, mert minden esetben fel lehet írni ezt az egyenletet:


(4x-27)/84 = k, ahol k egész (vagy y, ha az jobban tetszik). Ezt az egyenletet át tudjuk ilyen alakra rendezni:


4x-84k = 27


Itt ki tudunk emelni 2-t:


2*(2x+41k) = 27, majd oszthatunk 2-vel:

2x+41k = 27/2

Értelemszerűen egész számok összege nem lehet tört, így ennek nincs megoldása (ZxZ-ben).


2. Követhetjük ugyanazt a stratégiát, mint fent:


(4x-27)/43 = k, rendezés után

4x-43k = 27, ez gyakorlatilag ugyanaz az egyenlet, amit te felírtál. Mivel itt nem tudunk kiemelni, ezért jó eséllyel lesz megoldás is. Rendezzük x-re:


x = (27+43k)/4, azt kell elérnünk, hogy a jobb oldal egész legyen. Saját érdekünkben érdemes egy kicsit bírkózni még vele; maradékosan osztunk 4-gyel:


x = 6 + 10k + (3+3k)/4, itt akár ki is emelhetünk még 3-at:

x = 6 + 10k + 3*(k+1)/4, itt pedig már nem nehéz rájönni, hogy a k=3;7;10;... számok lesznek jók, vagyis a k=4n+3 alakúak, ahol n tetszőleges egész szám. Ezt még beírjuk k helyére:


x = 6 + 10*(4n+3) + 3*(4n+3+1)/4 = 6 + 40n+30 + 3n+3 = 43n+39, ez lesz a kongruencia megoldása. Ellenőrzés:


4*(43n+39) = 27 mod(43), kibontjuk a zárójelet:

172n+156 = 27 mod(43), kivonunk 27-et:

172n+129 = 0 mod(43), a bal oldali összeg osztható 43-mal (így kongruens 0), tehát jól számoltunk.


Valószínűleg teljesen máshogy tanítják ennek a megoldását. Sajnos én nem voltam nagy számelméletes, így én csak így tudom megoldani.


3. Ha ugyanúgy járunk el:


(4x-26)/82 = k, ahol k egész, x-re rendezés után

x = (82k+26)/4 = (41k+13)/2 = 20k + 6 + (k+1)/2, innen k=1;3;5;...=2n+1, ahol n tetszőleges egész, így

x = 20*(2n+1) + 6 + (2n+1+1)/2 = 40n+20 + 6 + n+1 = 41n + 27, ez a végeredmény.


Ellenőrzés:


4*(41n+27) = 26 mod(82), zárójelbontás

164n+108 = 26 mod(82), kivonunk 26-ot

164n+82 = 0 mod(82), a bal oldal osztható 82-vel, tehát jól számoltunk.

okt. 14. 21:39
Hasznos számodra ez a válasz?
 2/4 A kérdező kommentje:
Köszönöm szépen a választ! Az nem világos nekem, hogy aszerint, amit írtál, végtelen megoldásunk van, nem? Mert n lehet bármely természetes szám. Itt például beszélnek megoldások számáról [link] de ezt a példát is meg lehet oldani úgy, hogy végtelen legyen. Ahogy írtad.
okt. 14. 23:11
 3/4 anonim ***** válasza:

A linkelt videón csak pár, egymást követő megoldást írt fel. Ha jól értem, azt is mondja a végén, hogy azokat csak példának írta fel.

Ha kongruenciával adjuk meg a megoldást, akkor csak elég annyit írni, hogy

x kongruens 3 mod(5), ami magában foglalja az összes megoldást, elvégre x helyére végtelen sok szám írható. Egyenlőségként úgy írhatjuk fel, hogy x=3+5n, ahol n tetszőleges egész.

„Megoldás számossága” alatt azt szokták érteni, hogy hányféle olyan megoldás van, amik nem esnek egy maradékosztályba. Tudtommal lineáris kongruenciáknál csak egyféle megoldás van (ami végtelen sok számot tartalmaz), vagy nem megoldható. Illetve olyan lehet, hogy minden egész szám a megoldása, az viszont tekinthető a mod(1) maradékosztály számainak.

okt. 14. 23:35
Hasznos számodra ez a válasz?
 4/4 A kérdező kommentje:
Áhh, értem! Azt hiszem. :) Köszi!
okt. 14. 23:46

További kérdések:





Minden jog fenntartva © 2020, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | WebMinute Kft. | Facebook | Kapcsolat: info@gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!