Search

Neka su $a$ i $b$ relativno prosti prirodni brojevi različiti od $1$. Definiran je niz $$x_1 = a, \qquad x_2 = b, \qquad x_n = \frac{x_{n-1}^2 + x_{n-2}^2}{x_{n-1} + x_{n-2}} \quad \text{za } n \geq 3.$$

Dokaži da niti jedan član $x_n$ ovog niza, osim prva dva, nije prirodni broj.

Za dani prirodni broj $k$ neka je $S(k)$ zbroj svih brojeva iz skupa $\{1,2,\ldots,k\}$ koji su relativno prosti s $k$. Neka je $m$ prirodni i $n$ neparni prirodni broj. Dokaži da postoje prirodni brojevi $x$ i $y$, pri čemu $m$ dijeli $x$, takvi da vrijedi $2S(x) = y^n$.

Neka je $f: \mathbb{N} \to \mathbb{N}$ multiplikativna funkcija takva da je $f(4) = 4$ i vrijedi $$f(m^2 + n^2) = f(m^2) + f(n^2) \quad \text{za sve } m, n \in \mathbb{N}.$$

Dokaži da je $f(m^2) = m^2$ za sve $m \in \mathbb{N}$.

Za funkciju $f$ kažemo da je multiplikativna ako za svaki izbor relativno prostih prirodnih brojeva $m$ i $n$ vrijedi $f(mn) = f(m)f(n)$.

Neka je $x$ prirodan broj. Pretpostavimo da postoje dva relativno prosta prirodna broja $m$ i $n$ za koje su brojevi $x^3 + mx$ i $x^3 + nx$ kvadrati prirodnih brojeva. Dokaži da postoji beskonačan skup prirodnih brojeva $S$ takav da su svi članovi skupa $S$ u parovima relativno prosti, te je $x^3 + kx$ kvadrat prirodnog broja za svaki $k \in S$.

Za tročlani podskup skupa prirodnih brojeva kažemo da je jeftin ako u njemu postoje dva broja koja su relativno prosta te dva broja od kojih jedan dijeli drugoga.

Dan je prirodni broj $n$. Koliko najviše jeftinih tročlanih podskupova može imati skup koji sadrži točno $2n + 1$ prirodnih brojeva?

Prove that the fraction $\frac{21n+4}{14n+3}$ is irreducible for every natural number $n$.

Prove that the set of integers of the form $2^k - 3$ $(k = 2, 3, \ldots)$ contains an infinite subset in which every two members are relatively prime.

Let $a, b$ and $c$ be positive integers, no two of which have a common divisor greater than 1. Show that $2abc - ab - bc - ca$ is the largest integer which cannot be expressed in the form $xbc + yca + zab$, where $x, y$ and $z$ are non-negative integers.

Let $n$ and $k$ be given relatively prime natural numbers, $k < n$. Each number in the set $M = \{1, 2, \ldots, n-1\}$ is colored either blue or white. It is given that

• (i) for each $i \in M$, both $i$ and $n-i$ have the same color;

• (ii) for each $i \in M, i \neq k$, both $i$ and $|i-k|$ have the same color.

Prove that all numbers in $M$ must have the same color.

Let $n > 6$ be an integer and $a_1, a_2, \ldots, a_k$ be all the natural numbers less than $n$ and relatively prime to $n$. If

$$a_2 - a_1 = a_3 - a_2 = \cdots = a_k - a_{k-1} > 0,$$

prove that $n$ must be either a prime number or a power of 2.

Let $S = \{1, 2, 3, \ldots, 280\}$. Find the smallest integer $n$ such that each $n$-element subset of $S$ contains five numbers which are pairwise relatively prime.

Determine all positive integers relatively prime to all the terms of the infinite sequence $$a_n = 2^n + 3^n + 6^n - 1, \quad n \geq 1.$$

An ordered pair $(x, y)$ of integers is a primitive point if the greatest common divisor of $x$ and $y$ is 1. Given a finite set $S$ of primitive points, prove that there exist a positive integer $n$ and integers $a_0, a_1, \ldots, a_n$ such that, for each $(x, y)$ in $S$, we have:

$$a_0 x^n + a_1 x^{n-1} y + a_2 x^{n-2} y^2 + \cdots + a_{n-1} x y^{n-1} + a_n y^n = 1.$$

In each vertex of a regular $n$-gon there is a fortress. At the same moment each fortress shoots at one of the two nearest fortresses and hits it. The result of the shooting is the set of the hit fortresses; we do not distinguish whether a fortress was hit once or twice. Let $P(n)$ be the number of possible results of the shooting. Prove that for every positive integer $k \geq 3$, $P(k)$ and $P(k + 1)$ are relatively prime.

Find all pairs of positive integers $(m,n)$ for which there exist relatively prime integers $a$ and $b$ greater than $1$ such that $$\frac{a^m + b^m}{a^n + b^n}$$ is an integer.

Neka su $m$ i $n$ prirodni brojevi, $a = (n + 1)^m - n$ i $b = (n + 1)^{m+3} - n$.

(a) Dokažite da su $a$ i $b$ relativno prosti ako $m$ nije djeljiv s $3$.

(b) Odredite sve brojeve $m$ i $n$ za koje $a$ i $b$ nisu relativno prosti.

Dano je $10$ složenih prirodnih brojeva manjih od $840$. Dokaži da među njima postoje barem dva broja koja nisu relativno prosta.

a) Dokaži da za međusobno različite prirodne brojeve $a$ i $b$ postoji beskonačno mnogo prirodnih brojeva $n$ takvih da su brojevi $a + n$ i $b + n$ relativno prosti.

b) Postoje li međusobno različiti prirodni brojevi $a$, $b$, $c$ i $d$ za koje ne postoji prirodni broj $n$ takav da su brojevi $a + n$, $b + n$, $c + n$, $d + n$ u parovima relativno prosti?

Žaba Žana nalazi se ishodištu brojevnog pravca, te u svakom koraku skače za jedan ulijevo, za jedan udesno ili ostaje na mjestu. Lina i Dina izabrale su relativno proste brojeve $m$ i $n$, gdje je $m > n$. Nakon svakih $n$ koraka Lina zapovijeda: „Lijevo!", a nakon svakih $m$ koraka Dina zapovijeda: „Desno!" Žana miruje dok ne čuje prvu zapovijed, a nakon toga počinje (ili nastavlja) skakati u smjeru prema zapovijedi. Zaustavlja se u prvom koraku u kojem čuje obje zapovijedi. U ovisnosti o brojevima $m$ i $n$ odredi na kojoj se udaljenosti od ishodišta Žana zaustavila.

Neka je $f(x) = x^{2002} - x^{2001} + 1$. Dokazati da su za svaki prirodan broj $m$ brojevi $m$, $f(m)$, $f(f(m))$, $f(f(f(m)))$, ..., u parovima relativno prosti, tj. da nikoja dva među njima nemaju zajednički djelitelj veći od $1$.

Niz $(a_n)$ zadan je rekurzivno: $$\begin{aligned} a_0 &= 3 \\ a_n &= 2 + a_0 \cdot a_1 \cdot \dots \cdot a_{n-1}, \quad n \geq 1. \end{aligned}$$

a) Dokažite da su svi članovi tog niza u parovima relativno prosti prirodni brojevi.

b) Odredite $a_{2007}$.

Za dani prirodni broj $n$ neka je $M(n)$ najveći prirodni broj za koji je moguće konstruirati niz prirodnih brojeva $x_{1},x_{2},\ldots ,x_{M(n)}\in \{2,3,\ldots ,n\}$ tako da vrijedi:

Za svaka dva različita broja $i,j\in \{1,2,\ldots ,M(n)\}$ brojevi $2^{x_i} - 1$ i $2^{x_j} - 1$ su relativno prosti.

Ako je $M(k) = M(k - 1)$ za neki prirodni broj $k > 1$, dokaži da je $k$ složen.

Za dva polja tablice $10 \times 10$ kažemo da su prijateljska ako imaju barem jedan zajednički vrh. U svako polje tablice upisan je po jedan prirodni broj manji ili jednak $10$, tako da su brojevi u prijateljskim poljima relativno prosti. Dokaži da postoji broj koji se pojavljuje u toj tablici barem $17$ puta.

Dokaži da bilo koji $2001$-člani podskup skupa $\{1,2,3,\ldots,3000\}$ sadrži tri elementa od kojih su svaka dva međusobno relativno prosta.

Rudi i Miljen igraju igru na školskoj ploči naizmjence odigravajući poteze. Igrač koji je na potezu bira dva relativno prosta broja napisana na ploči, briše ih te zapisuje na ploču njihov zbroj. Gubi igrač koji to ne može napraviti. Igru započinje Rudi. Dokaži da Miljen ima pobjedničku strategiju ako je na početku na ploči bilo napisano

(a) 2019 jedinica;

(b) 2020 jedinica.