Van-e olyan x és y természetes szám, amelyre teljesül, hogy a 17 osztója a 20x-11y-nak, de nem osztója a 46x + 7y-nak?

"Ha 20x-11y osztható 17tel, akkor 3x-11ynak is oszthatónak kell lennie 17tel. Eddig értem. Azután az x miért 17n+a?"

A 17n+a azoknak a számoknak az általános alakja, amik 17-tel osztva "a"-t adnak maradékul. Az "n" egy tetszőleges egész szám. Ha mondjuk a=2, akkor 17n+a alakú lesz a 2, a 19, de a 36 is. Ugyanabba a maradékosztályba tartoznak ezek a számok a 17-tel való oszthatóság szempontjából. A megoldásnak az a "lelke", hogy a maradékosztályok minden tagja pontosan ugyanúgy viselkedik oszthatóság szempontjából, egymással cserélhetők. Magyarul a 2*16 ugyanannyi maradékot ad 17-tel osztva, mint a 19*33, vagy a 36*50 (azt is mondjuk, 2*16 ≡ (kiejtve: kongruens) 36*50 modulo 17).

Üdv, a macskás :D

Például egy egyszerű megoldás: Azt használja, amit a 2-es hozzászólásban leírtam.

20x-11y // -17x + 17y (17-el osztható számot vonunk le és adunk hozzá. Osztható marad.)

3x+6y // /3 (Ha hárommal osztunk, ami 17-hez képest reltív prím, nem változik az oszthatóság.)

x+2y (Egy egyszerű kifejezés, amiről beláttuk, hogy osztható 17-tel.)

46x+7y // -46(x+2y) (Levonjuk a 17-tel osztható szám 46 szorosát. 46 és 17 relatív prím. Az eredmény oszthatósága nem változik.)

-85y=-5*17*y (A keletkező szám osztható 17-tel, vagyis 46x+7y is osztható volt.)

"(Levonjuk a 17-tel osztható szám 46 szorosát. 46 és 17 relatív prím. Az eredmény oszthatósága nem változik.)"

Erre nincs is szükség. Elég annyi, hogy -46(x+2y) osztható 17-tel, mert (x+2y) osztható.

A #3-as vagyok.

Két kifejezésből indult el a feladat. Az egyik a 20x-11y volt, amiről beláttuk, hogy a 17-tel való oszthatóság szempontjából egyenértékű a 3x-11y kifejezéssel. Itt x és y ugye egész számok, és egyikük sem lehet 17-tel osztható (hiszen ha azok lennének, akkor a 46x+7y is osztható lenne 17-tel, és pont ezt akarnánk elkerülni). Írjuk fel az x-et és az y-t általános alakban. Ha az x 17-tel osztva "a", az y pedig "b" maradékot ad, akkor x=17n+a és y=17m+b (ahol n és m egész számok).

Most nézzük meg újra a 3x-11y kifejezést. Mikor lesz ez 17-tel osztható? Pontosan akkor, ha a 3x és a 11y ugyanazt a maradékot adja 17-tel osztva (mert a kivonás elvégzésekor ez a maradék eltűnik, és ami ott marad, az 17 többszöröse lesz).

Most nézzük meg ugyanezt a fentebb említett általános alakkal, ahol x=17n+a és y=17m+b. 3x = 3*(17n+a) = 3*17n+3a. Ez milyen maradékot ad 17-tel osztva? Annyit, amennyit a 3a. 11y = 11*(17m+b) = 11*17m + 11b. Ez 17-tel osztva annyi maradékot ad, mint 11b.

Vagyis 3a ≡ 11b modulo 17 (ha 3a és 11b nem is feltétlenül egyenlőek, ugyanabba a maradékosztályba tartoznak, mert 17-tel osztva ugyanazt a maradékot adják). 12a ≡ 44b modulo 17, mert 3*3a pedig ugyanazt a maradékot adja 17-tel osztva, mint 3*11b.

46x + 7y ≡ 12x + 7y modulo 17 (mert a 17-tel garantáltan osztható 34x-et szabadon levonhatjuk a kifejezésből). Ha ide (a 12x + 7y kifejezésbe) behelyettesítesz az általános alakkal (x=17n+a; y=17m+b), és a 12a helyett 44b-t írsz (amit szintén megtehetsz, mert a maradékosztályok tagjai egymással helyettesíthetők), megkapod a végeredményt.

20x-11y \*4

80x-44y \-46x-7y

34x-51y=17*(2x-3y)

Ez utóbbi osztható 17-tel, azonban a különbség maradéka a maradékok különbsége, azaz a 46x+7y is osztható kell legyen 17-tel.

#18

Szép, tömör bizonyítás. :-)