#brojevi

Broj x možemo zapisati u obliku x=abcdef, a množenjem dobijamo:

\[ \] \[ 2\cdot x=a2b2c2d2e2f2 \] \[ 3\cdot x=a3b3c3d3e3f3\] \[ 4\cdot x=a4b4c4d4e4f4\] \[ 5\cdot x=a5b5c5d5e5f5\] \[ 6\cdot x=a6b6c6d6e6f6\] \[ \] \[ \]

U proizvodima se pojavljuju cifre a,b,c,d,e i f na različitim mestima, pa ćemo sabirajući leve i desne strane prethodnih jednakosti dobiti:

\[ \] \[ x+2\cdot x+3\cdot x+4\cdot x+5\cdot x+6\cdot x = \] \[ 100000\cdot a+10000\cdot a+1000\cdot a+100\cdot a+10\cdot a+a+ \] \[ 100000\cdot b+10000\cdot b+1000\cdot b+100\cdot b+10\cdot b+b+ \] \[ 100000\cdot c+10000\cdot c+1000\cdot c+100\cdot c+10\cdot c+c+ \] \[ 100000\cdot d+10000\cdot d+1000\cdot d+100\cdot d+10\cdot d+d+ \] \[ 100000\cdot e+10000\cdot e+1000\cdot e+100\cdot e+10\cdot e+e+ \] \[ 100000\cdot f+10000\cdot f+1000\cdot f+100\cdot f+10\cdot f+f \] \[ 21\cdot x=111111\cdot \left(a+b+c+d+e+f\right) \] \[ x=\left(111111\cdot\left(a+b+c+d+e+f\right)\right)\div 21 \] \[ x=5291\cdot \left(a+b+c+d+e+f\right) \] \[ \] \[ \]

Pogledaćemo poslednju cifru f i pretpostavićemo da je neki element skupa A={1,2,3,4,5,6,7,8,9} i proverićemo da li se množenjem sa nekim od brojeva 2,3,4,5,6 dobija ista cifra jedinica u nastalom proizvodu.

\[ \] \[ 1\cdot x=x \] \[ 2\cdot 6=12 \] \[ 4\cdot 6=24 \] \[ 5\cdot 5=25 \] \[ 6\cdot 6=36 \] \[ 8\cdot 6=48 \] \[ \] \[ \]

Navedene cifre ne mogu biti f (množenjem sa nekim od brojeva 2,3,4,5,6 dobija ista cifra jedinica u nastalom proizvodu), pa zaključujemo da je f iz skupa B={3,7,9}. Cifre jedinica proizvoda traženog broja sa brojevima 2,3,4,5,6 u tim slučajevima su:

\[ \] \[ f=3\] \[ 3\cdot 2\implies poslednja \\ cifra \\ rezultata \\ je \\ 6\] \[ 3\cdot 3\implies poslednja \\ cifra \\ rezultata \\ je \\ 9\] \[ 3\cdot 4\implies poslednja \\ cifra \\ rezultata \\ je \\ 2\] \[ 3\cdot 5\implies poslednja \\ cifra \\ rezultata \\ je \\ 5\] \[ 3\cdot 6\implies poslednja \\ cifra \\ rezultata \\ je \\ 8\] \[ \] \[ f=7\] \[ 7\cdot 2\implies poslednja \\ cifra \\ rezultata \\ je \\ 4\] \[ 7\cdot 3\implies poslednja \\ cifra \\ rezultata \\ je \\ 1\] \[ 7\cdot 4\implies poslednja \\ cifra \\ rezultata \\ je \\ 8\] \[ 7\cdot 5\implies poslednja \\ cifra \\ rezultata \\ je \\ 5\] \[ 7\cdot 6\implies poslednja \\ cifra \\ rezultata \\ je \\ 2\] \[ \] \[ f=9\] \[ 9\cdot 2\implies poslednja \\ cifra \\ rezultata \\ je \\ 8\] \[ 9\cdot 3\implies poslednja \\ cifra \\ rezultata \\ je \\ 7\] \[ 9\cdot 4\implies poslednja \\ cifra \\ rezultata \\ je \\ 6\] \[ 9\cdot 5\implies poslednja \\ cifra \\ rezultata \\ je \\ 5\] \[ 9\cdot 6\implies poslednja \\ cifra \\ rezultata \\ je \\ 4\] \[ \] \[ \]

Cifra "a" mora biti 1, jer se samo u tom slučaju pri množenju sa 6 dobija šestocifreni broj. Zaključujemo da je f=7 jer se jedino u tom slučaju pojavljuje cifra 1 na poslednjem mestu (sve poslednje cifre su očigledno različite i uključujući cifru f=7 obuhvataju svih šest traženih cifara broja x). Sabiranjem poslednjih cifara svih dobijenih proizvoda za slučaj f=7, zaključujemo:

\[ \] \[ a+b+c+d+e = 4+1+8+5+2 = 20 \] \[ a+b+c+d+e+f = 27 \] \[ \]

Iz toga dalje logično sledi:

\[ \] \[ x = 5291 \cdot 27 \] \[ x = 142857 \] \[ \] \[ \]

Provera:

\[ \] \[ 142857 \cdot 2=285714 \] \[ 142857 \cdot 3=428571 \] \[ 142857 \cdot 4=571428 \] \[ 142857 \cdot 5=714285 \] \[ 142857 \cdot 6=857142 \]

Za dokaz ove teoreme biće potrebno dokazati da važi ako je \( a^{b}\equiv c (mod n) \) onda je \( (a^{b})^{d}\equiv c^{d} (mod n) \). Pošto važi \( a^{b}\equiv c (mod n) \) možemo zapisati \( a^{b}= k\times n+c \). Kada ovo zamenimo u jednakost \( (a^{b})^{d}\equiv c^{d} (mod n) \) dobijamo \( ( k\times n+c)^{d}=c^{d} (mod n) \). Poznato nam je da je \( ( k\times n+c)^{d}=\sum_{p=0}^{d}\times {\displaystyle {d \choose p}}\times (k\times n)^{d-p}\times c^{p} \). Svaki član ovog proizvoda biće kongruentan sa 0 po modulu n osim onog kada je p=d kada je član ovog proizvoda \( c^{d} \) tj. ovaj proizvod je kongruentan sa \( c^{d} \) po modulu n a to je ono što je trebalo da dokažemo. Da bismo dokazali traženu teoremu naći ćemo ostatke pri deljenju stepena brojeva 3 i 4 sa 13.

\[ 3^{1}\equiv 3 (mod 13) \] \[ 3^{2}\equiv 9 (mod 13) \] \[ 3^{3}\equiv 1 (mod 13) \]

Sada ćemo primeniti teoremu koju smo gore dokazali. Pošto nam je c=1 važi da je \((3^{3})^{35}\equiv 1^{35}=1 \) (mod 13) tj. \( 3^{105}=13\times q+1 \).

\[ 4^{1}\equiv 4 (mod 13) \] \[ 4^{2}\equiv 3 (mod 13) \] \[ 4^{3}\equiv 12 (mod 13)\equiv -1 (mod 13) \]

Opet ćemo primeniti navedenu teoremu. Pošto nam je c=-1 važi da je \( (4^{3})^{35}\equiv (-1)^{35}=-1 (mod 13) \) tj.\( 4^{105}= 13\times s-1 \).

\[ 3^{105}+4^{105}= 13\times q+1+13\times s-1 =13\times q+ 13\times s=13\times (q+s) \]

Pošto se broj \( 3^{105}+4^{105} \) može zapisati u obliku proizvoda nekog prirodnog broja sa 13 broj \( 3^{105}+4^{105} \) deljiv je brojem 13. Da bismo dokazali da broj \( 3^{105}+4^{105} \) nije deljiv sa 11 naći ćemo ostatke pri deljenju stepena brojeva 3 i 4 sa 11.

\[ 3^{1}\equiv 3 (mod 11) \] \[ 3^{2}\equiv 9 (mod 11) \] \[ 3^{3}\equiv 5 (mod 11) \] \[ 3^{4}\equiv 4 (mod 11) \] \[ 3^{5}\equiv 1 (mod 11) \]

Sada ćemo ponovo primeniti dokazanu teoremu. Pošto nam je c=1 važi da je \( (3^{5})^{21}\equiv 1^{21}= 1 (mod 11) \) tj. \( 3^{105}=11\times x+1 \).

\[ 4^{1}\equiv 4 (mod 11) \] \[ 4^{2}\equiv 5 (mod 11) \] \[ 4^{3}\equiv 9 (mod 11) \] \[ 4^{4}\equiv 3 (mod 11) \] \[ 4^{5}\equiv 1 (mod 11) \]

Pošto je c=1 važi da je \( (4^{5})^{21}\equiv 1^{21}=1 (mod 11) \) tj. \( 4^{105}= 11\times y+1 \).

\[ 3^{105}+4^{105}=11\times x+1 + 11\times y+1 = 11\times (x+y)+2 \]

Zato što se broj \( 3^{105}+4^{105} \) može zapisati u obliku zbira proizvoda nekog prirodnog broja sa 11 i broja 2, broj \( 3^{105}+4^{105} \) nije deljiv sa 11 tj. daje ostatak 2 pri deljenju sa 11.

Dati broj može se predstaviti kao \( 100a + 10b + c \). Zbir cifara ovog broja predstavljamo kao \( a+b+c = 10 \).

Broj je deljiv sa 11 ako je razlika zbira cifara na parnim pozicijama i zbira cifara na neparnim pozicijama, deljiva sa 11. Pošto je ovaj broj deljiv sa 11, a ima samo tri cifre, jedina moguća opcija je \( b - (a + c) = 0 \), pa važi \( a+c = b \).

Sada ćemo drugi izraz ubaciti u prvi:

\[ a+b+c = 10 \] \[ 2b = 10 \] \[ b = 5 \]

Dobili smo da je cifra b u broju jednaka 5, što znači da je \( a+c = 5 \).

Pošto je zbir cifara a i c jednak 5, imamo tri moguće kombinacije: 1 i 4, 2 i 3, 5 i 0.

Za prvi i drugi sluèaj imamo po dva broja, a za treći samo jedan (nula ne može biti na poèetku broja). Ukupno ima 5 traženih brojeva. To su: 154, 451, 253, 352 i 550.

\[ 10! = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \]

Razmotrićemo ostatke pri deljenju odredjenih proizvoda sa 11:

\[ 1 \cdot 10 = 10 \] \[ 10 \equiv 10( \bmod 11) \] \[ 2 \cdot 6 = 12 \] \[ 12 \equiv 1( \bmod 11) \] \[ 3 \cdot 4 = 12 \] \[ 12 \equiv 1( \bmod 11) \] \[ 7 \cdot 8 = 56 \] \[ 56 \equiv 1( \bmod 11) \] \[ 5 \cdot 9 = 45 \] \[ 45 \equiv 1( \bmod 11) \] \[ \] \[ 10! \equiv (10 \cdot 1 \cdot 1 \cdot 1 \cdot 1)( \bmod 11) \] \[ 10! \equiv 10( \bmod 11) \]

Ostatak pri deljenju 10! sa 11 je 10

Treba ispitati da li za svaki broj zapisan u obliku \( \bar{abcabc} \) važi da je deljiv sa 7, 11, 13.

\[ \bar{abcabc} = \] \[ 100000a + 10000b + 1000c + 100a + 10b + c = \] \[ 100100a + 10010b + 1001c = \] \[ 13 \cdot (7700a + 770b + 77c) = \] \[ 13 \cdot 7 \cdot (1100a + 110b + 11c) = \] \[ 13 \cdot 7 \cdot 11 \cdot (100a + 10b + c) = \] \[ 1001 \cdot (\bar{abc}) \]

Dakle, broj datog oblika je deljiv sa 7,11 i 13.

Datih 12 prirodnih brojeva možemo rasporediti u 11 kategorija: brojevi deljivi sa 11 ili brojevi koji pri deljenju sa 11 daju neki ostatak od 1 do 10.

Kako imamo 12 brojeva a 11 kategorija, na osnovu Dirihleovog principa bar u jednoj kategoriji se nalaze dva broja. Ta dva broja imaju jednake ostatke pri deljenju sa 11.

To su brojevi: \( a = 11 \cdot x + r \) i \( b = 11 \cdot y + r \). Dalje zaključujemo:

\[ a-b = 11 \cdot x + r - 11 \cdot y - r \] \[ a-b = 11 \cdot x - 11 \cdot y \] \[ a-b = 11 \cdot (x-y) \]

Zaključujemo da važi 11|(a-b), što je i trebalo dokazati.

\[ 1+2+3+...+n = 100 \cdot a + 10 \cdot a + a \] \[ 1+2+3+...+n = 111 \cdot a \]

Iskoristiću Gausov postupak (sabraću prvi i poslednji, drugi i pretposlenji itd.):

\[ (n+1)+(n-1+2)+(n-2+3)+... = 111 \cdot a \] \[ (n \cdot (n+1)) \div 2 = 111 \cdot a \] \[ (n \div 2) \cdot (n+1) = 111 \cdot a \]

Rastavićemo 111 na proste činioce:

\[ 111 \div 3 = 37 \]

Što znači da je:

\[ 111 = 3 \cdot 37 \]

Pošto znamo da je \( (n \div 2) \cdot (n+1) \) deljivo sa 111, znači da je:

\[ n+1 = 3 \vee n+1 = 37 \]

Uz laku proveru možemo da zaključimo da je n=36, a traženi trocifren broj je:

\[ 18 \cdot 37 = 666 \]

Neka su traženi dvocifreni brojevi oblika \( \bar{ab} \) i \( \bar{cd} \). Tada, prema uslovima zadatka, važi:

\[ A = \bar{ab} \times \bar{cd} \] \[ B = \bar{ba} \times \bar{dc} \]

Transformisaćemo razliku A-B:

\[ (10a+b)(10c+d) - (10b+a)(10d+c) = \] \[ 100ac + 10ad + 10cb + bd - 100bd - 10bc - 10da - ac = \] \[ 100ac - ac + bd - 100bd = \] \[ 99ac - 99bd = \] \[ 99(ac-bd) \]

Nakon prethodnih transformacija zaključujemo da važi 99|A-B, što je i trebalo dokazati.