Szamelmeleti feladat?

> „Bármely pozitív n? Akkor az lehet 5 is.”

Igen, így van. Ehhez az n-hez kell találnod k-t, hogy n*k = 5*k egy olyan szám, hogy csak 3-asok és 0-k vannak benne. Például a k = 6 ilyen, mert 6*5 = 30. (De jó például k = 60 vagy a k = 606, elég annyi, hogy van ilyen.)

Ugyanígy meg kell mutatnod, hogy van megfelelő k az n = 1, n = 2, n = 3,… számokhoz is.

Volt már korábban kérdés, illetve ott az volt az állítás, hogy minden számnak van csak 0-kat és 1-eket tartalmazó többszöröse. Én akkor így bizonyítottam;

Vizsgáljuk a helyiértékek, vagyis az 1;10;100;1000;... számok n-nel vett maradékait. Két csoportba tudjuk tenni a számokat;

-Az egyik csoportba azok az n-ek tartoznak, amelyek az 1;10;100;1000; ... számok valamelyikének osztója. Az ilyen számoknál nem nehéz rájönni, hogy a keresett szám 1000.... alakú lesz. Ilyen szám például a 125, ez a szám az 1000-et (és az ennél nagyobbakat) osztja, tehát a 125-höz az 1000 jó lesz. Nyilván az eredeti feladat szempontjából csak annyi a dolgunk, hogy 3-mal szorzunk, minden esetben.

-A másik csoportban azok a számok foglalnak helyet, amelyek nem osztják az 1;10;100;1000;... számok egyikét sem. Azt kell kihasználnunk, hogy ha egy összeg osztható egy számmal, akkor a tagok maradékainak összege is osztható a számmal. Például 16+77+39=132, ez a szám osztható 3-mal, a tagok 3-as maradékai: 1;2;0, ezek összege 3, ami osztható 3-mal, így az összeg is. Tehát arra hajtunk, hogy az 1;10;100;1000;.... számok n-nel vett maradékaiknak összege osztható legyen n-nel. Ez pedig kivitelezhető; tudjuk, hogy n akármekkora is legyen, biztosan lesz olyan maradék, amely tetszőlegesen sokszor (végtelenszer) ismétlődni fog. Ezt nem nehéz belátni;

Azt biztos, hogy a maradékok kisebbek n-nél. Ha minden maradék véges sokszor szerepelne, akkor véges sok számot tudnánk csak felírni, viszont az 1;10;100;1000;... sorozat végtelen sok tagból áll, amikhez pedig mind-mind tartozik valamilyen maradék, ennek megfelelően ellentmondásra jutunk. Tehát lesz olyan maradék, amit végtelen sokszor kell felírnunk.

Ha ezekből a végtelen sokszor ismétlődő számokból kiválasztunk megfelelően sokat, és ezeket összeadjuk, akkor megkapjuk az állításnak megfelelő számot. Ha a maradékot M-mel jelöljük, akkor nem nehéz rájönni, hogy ha n darabot választunk belőlük, akkor n*M lesz a maradékok összege, ami osztható lesz n-nel, így a számok összege is, a többiből értelemszerűen 0 darabot veszünk. Így ha ezeket összeadjuk, akkor olyan n-nel osztható számot fogunk kapni, amelyben csak a 0;1 számjegyek szerepelnek. Itt is működik az, hogy egyszerűen szorzunk 3-mal, így a számjegyek 0;3 számjegyekké válnak.

Például vegyük a 7-et. Nézzük a számok 7-es maradékait:

1 : 7 maradéka 1

10 : 7 maradéka 3

100 : 7 maradéka 2

1000 : 7 maradéka 6

10000 : 7 maradéka 4

100000 : 7 maradéka 5

1000000 : 7 maradéka 1

Most fogadjuk el, hogy innentől kezdve a maradékok ciklikusan követni fogják egymást (mivel a bizonyításnál ezt nem használtam), tehát az 1;3;2;6;4;5 számsor szerint fognak váltakozni. Tehát mindegyik maradék végtelen sokszor szerepelni fog. Ennek megfelelően kiválaszthatjuk bármelyik maradékot. Például válasszuk a 6-ost. Ha ebből veszünk 7 darabot, akkor a maradékok összege 42 lesz, tehát az összeg osztható lesz 7-tel. Ezen okfejtés alapján az 100010000001000000100000010000001000000 szám osztható lesz 7-tel, és csak 0;1 számjegyeket tartalmaz. Ezt megszorozva 3-mal szintén 7-tel osztható számot kapunk és csak 0;3 számjegyeket fog tartalmazni.

Nézzünk egy másik számot, például a 9-et;

1 : 9 maradéka 1

10 : 9 maradéka 1

100 : 9 maradéka 1

És így tovább a végtelenségig. Tehát ebben az esetben csak az 1 maradékkal tudunk variálni. Ebből veszünk 9-et, így az 111111111 számot kapjuk. Ebben csak egyesek vannak, és kérdés, hogy a feladat ragaszkodik-e ahhoz, hogy mindkét számjegyből legyen. Szerencsére ez nem probléma, ugyanis elég csak egy 0-t írni a szám végére, így kapjuk az 1111111110 számot, így már minden feltételt teljesítettünk. Ezt 3-mal szorozva megkapjuk a mostani feladathoz szükséges számot.

Tehát bármelyik pozitív n-hez található megfelelő többszörös. Az állítás szempontjából az az érdekesség, hogy itt nem egy konkrét számítást adtunk meg a k-ra (tehát nem egy függvényt adtunk meg, amivel bármilyen n számra megkapható a megfelelő k), hanem általánosságban válaszoltunk, hogy mindig létezik megfelelő k.

Persze lehet máshogyan is bizonyítani, én ezt találtam.

Minden természetes szám felírható n = (2^k)*(5^l)*m alakban, ahol k, l ≥ 0 és (m, 10) = 1. Először belátjuk, hogy a fenti m számnak van olyan többszöröse, ami csak 1-esekből és 0-kból áll. Erre jó lesz az u:= 10^(m*φ(m)) + 10^((m-1)*φ(m)) + ... + 10^(φ(m)) szám, hiszen az Euler-Fermat tétel miatt u ≡ m*1 ≡ 0 mod (m). Legyen d:= max{k, l}, ekkor 3*(10^d)*u megfelel a feltételeknek.

[link]