Koło matematyczne I LO w Białymstoku

 
Zadania PDF.

Źródło zadań w texu.

 
%        File: kongr.tex
%     Created: Mon Sep 05 09:00 AM 2011 C
% Last Change: Mon Sep 05 09:00 AM 2011 C
\documentclass[10pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\textwidth 16cm
\textheight 24cm
\oddsidemargin 0cm
\topmargin 0pt
\headheight 0pt
\headsep 0pt
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{polski}
\usepackage{import}
%\usepackage{MnSymbol}
% ----------------------------------------------------------------
\vfuzz4pt % Don't report over-full v-boxes if over-edge is small
\hfuzz4pt % Don't report over-full h-boxes if over-edge is small
% THEOREMS -------------------------------------------------------
\newtheorem{thm}{Twierdzenie}[section]
\newtheorem{cor}[thm]{Wniosek}
\newtheorem{lem}[thm]{Lemat}
\newtheorem{defn}[thm]{Definicja}
\newtheorem{tozs}[thm]{Tożsamość}
\newtheorem{hyp}[thm]{Hipoteza}
\newtheorem{example}[thm]{Przykład}
\newtheorem{useless}[thm]{}
 
\newenvironment{proof}[1][Dowód. ]{\noindent\textsc{#1}}
{\nolinebreak[4]\hfill$\blacksquare$\\\par}
\newenvironment{sol}[1][Rozwiązanie. ]{
\noindent\textsc{#1}}
{\hfill\par}
 
\newcounter{problem}
\newenvironment{problem}[1][Zadanie]{
\stepcounter{problem}
\noindent{\textsc{\bfseries #1 \theproblem}}\\}
{\hfill\par}
 
\def\deg{^{\circ}}
\def\source#1{\\Źródło: #1}
 
\renewcommand{\thethm}{}
\renewcommand{\angle}{\sphericalangle}
\renewcommand{\vec}[1]{\overrightarrow{#1}}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\dots}{\ldots}
 
\subimport{../}{style.sty}
 
%\def\teddy{\includegraphics{teddy_bear_small.png}}
 
\def\headpicture{../micek-2cm.jpg}
\def\author{Joachim Jelisiejew}
\def\date{6 września 2011}
\begin{document}
\section{Kongruencje}
 
Typ problemu:
 
\begin{minipage}{0.5\textwidth}
\begin{problem}
Oblicz ostatnią cyfrę liczb:
\begin{enumerate}
    \item $2^2 + 1^2,$
    \item $1202^2 + 61^2$,
    \item $7^4\cdot 2^5$,
    \item $34067\cdot 2345$,
    \item $5^4\cdot 3^6 + 6^3$,
    \item $\star\ \ 2^{32}$,
    \item $\star\ \ 2^{100}$,
    \item $\star\ \ 2^{2^{100}}$,
\end{enumerate}
\end{problem}
\end{minipage}\begin{minipage}{0.5\textwidth}
\begin{problem}
Oblicz resztę z~dzielenia przez $3$ liczb:
\begin{enumerate}
    \item $2^2 + 1^2,$
    \item $1202^2 + 61^2$,
    \item $7^4\cdot 2^5$,
    \item $34067\cdot 2345$,
    \item $5^4\cdot 2^6 + 7^3$,
    \item $\star\ \ 2^{32}$,
    \item $\star\ \ 2^{100}$,
    \item $\star\ \ 2^{2^{100}}$,
\end{enumerate}
\end{problem}
\end{minipage}
 
Podajemy tutaj zapis, który może wydawać się straszny, ale w~rzeczywistości
jest bardzo wygodny.
 
Wszystkie liczby w~poniższych definicjach są całkowite.
\begin{defn}
    Mówimy, że \emph{$a$ przystaje do $b$ modulo $n$}, jeżeli liczby $a, b$
    dają taką samą resztę z~dzielenia przez $n$, innymi słowy, gdy $n\big|a -
    b$. Oznaczamy tę sytuację $a\equiv b \mod n$.
 
    Pewne zastanawiające własności są takie:
    \begin{enumerate}
        \item jeżeli $a \equiv b \mod n$, to $b\equiv a \mod n$.
        \item jeżeli $a \equiv b \mod n$ i~$b\equiv c \mod n$, to $a \equiv c
            \mod n$.
    \end{enumerate}
\end{defn}
 
\begin{thm}
    Jeżeli $a \equiv b \mod n$ oraz $a'\equiv b' \mod n$, to
    \begin{enumerate}
        \item $a + a'\equiv b + b'\mod n$,
        \item $a - a'\equiv b - b'\mod n$,
        \item $a\cdot a' \equiv b \cdot b' \mod n$.
        \item $a^m \equiv b^m \mod n$, dla każdego $m$ naturalnego, np. $a^2
            \equiv b^2 \mod n$.
    \end{enumerate}
\end{thm}
 
\begin{example}
    Obliczyć resztę z~dzielenia przez $7$ liczby $45^3 \cdot 54^2$.
\end{example}
    \begin{sol}
        Trik polega na redukowaniu obliczeń do małych liczb:
 
        Zauważmy, że $45\equiv -4 \mod 7$ (bo $7\big|45 - (-4) = 49$), więc $45^3 \equiv (-4)^3 = -64 \mod
        7$. Ale $-64 \equiv -1 \mod 7$, więc $45^3 \equiv -1 \mod 7$.
 
        Analogicznie, obliczamy $54\equiv 5 \mod 7$, więc $54^2 \equiv 5^2 =
        25 \mod 7$. Ale $25 \equiv 4 \mod 7$, więc $54^2 \equiv 4 \mod 7$.
 
        Łącznie $45^3 \equiv -1 \mod 7$ i~$54^2 \equiv 4 \mod 7$, więc $45^3
        \cdot 54^2 \equiv -1\cdot 4 = -4 \mod 7$.
 
        Trzeba jeszcze zauważyć, że $-4 \equiv 3 \mod 7$.
 
        Odpowiedź: liczba $45^3 \cdot 54^2$ daje resztę $3$ z~dzielenia przez
        $7$.
    \end{sol}
 
\begin{problem}[$\star$ Zadanie]
    Dowiedź, że liczba $n$ daje taką samą resztę z~dzielenia przez $9$, jak
    suma cyfr $n$.
\end{problem}
\begin{problem}[$\star$ Zadanie]
    Dowiedź, że liczba $n$ daje taką samą resztę z~dzielenia przez $11$, jak
    cyfry $n$ zsumowane ze znakami $+$ i~$-$ na przemian: np. $123$ daje taką
    samą resztę jak $1 - 2 + 3 = 2$.
\end{problem}
 
\vskip 3cm
 
\end{document}