Zadanie 1

Iloczynem kartezjańskim grafów $G_1 = \langle V_1, E_1\rangle$ i $G_2 = \langle V_2, E_2\rangle$ nazywamy graf $G_1\otimes G_2 = \langle V_1\times V_2, E\rangle$, gdzie
$$\{\langle v_1,v_2\rangle,\langle w_1,w_2\rangle\} \in E \Leftrightarrow (\{v_1,w_1\} \in E_1 \wedge \{v_2,w_2\} \in E_2)\ .$$
Udowodnij, że graf $G_1\otimes G_2$ jest spójny wtedy i tylko wtedy, gdy obydwa grafy $G_1$ i $G_2$ są spójne i przynajmniej jeden z nich zawiera cykl nieparzystej długości.

Zadanie 2

Oblicz $7^{8^9} \bmod 100$.

Zadanie 3

Udowodnij uogólnione Chińskie Twierdzenie o Resztach: Niech $m_1,m_2>0$ niekoniecznie względnie pierwsze, $m = \mbox{NWW}(m_1,m_2)$. Wtedy dla dowolnych $u_1,u_2\geq 0$ istnieje dokładnie jedno u takie, że $0\leq u < m$ oraz $u \equiv u_i (\mbox{mod } m_i)$ dla i=1,2, o ile $u_1\equiv u_2 (\mbox{mod NWD}(m_1, m_2))$, a jeśli ten ostatni warunek nie jest spełniony, to takie u nie istnieje.