Koło matematyczne I LO w Białymstoku

 
Zadania PDF.

Źródło zadań w texu.

 
%        File: zad.tex
%     Created: nie maj 16 02:00  2010 C
% Last Change: nie maj 16 02:00  2010 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{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{useless}[thm]{}
\newtheorem{problem}[thm]{Zadanie}
\newenvironment{proof}[1][Dowód. ]{\noindent\textsc{#1}}
{\nolinebreak[4]\hfill$\blacksquare$\\\par}
\newenvironment{sol}[1][Rozwiązanie. ]{
\noindent\textsc{#1}}
{\par}
 
\def\rozw{$ $\\\textbf{Rozwiązanie}: \\}
\def\deg{^{\circ}}
 
 
\subimport{../}{style}
%\include{style}
\def\source#1{Źródło: #1}
 
\begin{document}
\renewcommand{\thethm}{}
\section{Mało zadań z małego twierdzenia Fermata}
 
\paragraph{Teoria}
\begin{enumerate}
    \item \begin{thm}[Małe twierdzenie Fermata]
            Jeżeli $p$ jest liczbą pierwszą, zaś $a$ jest liczbą całkowitą
            niepodzielną przez $p$, to
            $$a^{p-1} \equiv 1 \mod p.$$
        \end{thm}
    \item \begin{thm}[Małe twierdzenie Fermata, równoważnie]
            Jeżeli $p$ jest liczbą pierwszą, zaś $a$ jest liczbą całkowitą, to
            $$a^p \equiv a \mod p.$$
        \end{thm}
        \emph{Wypadł tutaj warunek $p\not|a$.}
    \item \begin{defn}
            Liczbę takich $a\in \left\{ 1,2,\dots,n \right\}$, że $a$ jest
            względnie pierwsze z $n$, oznaczam jako $\phi(n)$.
        \end{defn}
        \emph{Uwaga:} Załóżmy, że $n=p_1^{a_1} \cdot p_2^{a_2} \dots
        p_k^{a_k}$ jest rozkładem liczby $n$ na czynniki pierwsze. Wtedy
        $$\phi(n) = (p_1^{a_1} - p_1^{a_1 - 1})(p_2^{a_2} - p_2^{a_2 -
        1})\dots(p_n^{a_n} - p_n^{a_n - 1}).$$
        Np. $\phi(12) = \phi(2^2\cdot 3) = (2^2 - 2)(3-1) = 4$.
        Faktycznie liczby względnie pierwsze z $12$ i nie większe od $12$ to
        liczby $1,5,7,11$.
    \item \begin{thm}[Lagrange'a]
            Niech $n$ będzie liczbą naturalną, zaś $a$ liczbą całkowitą
            względnie pierwszą z $n$ tj. $NWD(a,n)=1$. Wtedy
            $$a^{\phi(n)} \equiv 1 \mod n,$$
            gdzie $\phi(n)$ jest zdefiniowane jak wyżej.
        \end{thm}
\end{enumerate}
 
\paragraph{Dowody teorii}
\begin{enumerate}
    \item Niech $p$ będzie liczbą pierwszą, zaś $a$ będzie liczbą niepodzielną
        przez $p$.
        \begin{enumerate}
            \item Dowiedź, że jeżeli $k,l\in \mathbb{Z}$ są takie, że
                $$ka \equiv la \mod p$$
                to $k \equiv l \mod p$.
            \item Uzasadnij, że 
                $$\{a \mod p, 2a\mod p,\dots, (p-1)a
                \mod p\} = \{1,2,\dots,p-1\}$$
                gdzie $x\mod p$ oznacza resztę z dzielenia $x$ przez $p$.
            \item Pokaż, że zachodzi
                $$a\cdot 2a\cdot 3a \cdot \ldots \cdot (p-1)a \equiv (p-1)!
                \mod p.$$
            \item Udowodnij małe twierdzenie Fermata (w 1.\ wersji).
            \item Udowodnij, że obie wersje małego twierdzenia Fermata są
                równoważne.
        \end{enumerate}
    \item Rozszerz powyższy dowód twierdzenia Fermata do dowodu twierdzenia
        Lagrange'a.
 
        \emph{Wskazówka: Jaki zbiór należy wziąć zamiast $\left\{ a\mod p, 2a \mod
        p,\dots,(p-1)a\mod p\right\}$?}
    \item Uzasadnij, że z twierdzenia Lagrange'a wynika małe
        twierdzenie Fermata.
\end{enumerate}
 
\paragraph{Zadania}
\begin{enumerate}
    \item Udowodnij, że jeżeli $n$ jest liczbą całkowitą, to
        $$30 | n^5 - n$$
    \item Niech $n\geq 1$ będzie liczbą naturalną, zaś $x_1,x_2,\dots,x_n$
        liczbami całkowitymi, których suma dzieli się przez $10$. Udowodnić,
        że liczba
        $$x_1^5 + x_2^5 + \dots + x_n^5$$
        jest również podzielna przez $10$.
 
        \source{PTM 2009, kl. I}
    \item Wykazać, że jeżeli $x$ i $y$ są liczbami całkowitymi, to liczba
        $$xy^5 - x^5y$$
        jest podzielna przez $30$.
 
        \source{PTM 2007, kl. I}
    \item Wykazać, że jeśli $p_1,p_2,\dots,p_{56}$ są liczbami pierwszymi
        większymi od $7$, to liczba
        $$p_1^6 + \dots + p_{56}^6$$
        jest podzielna przez $56$.
 
        \source{PTM 2005, kl. II}
 
        \emph{Uwaga: Przy dowodzeniu podzielności przez $8$ być może trzeba
        coś policzyć.}
 
\end{enumerate}
 
\end{document}