Koło matematyczne I LO w Białymstoku

 
Zadania PDF.

Źródło zadań w texu.

%        File: zad.tex
%     Created: Thu Oct 21 11:00 AM 2010 C
% Last Change: Thu Oct 21 11:00 AM 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]{}
 
\newenvironment{proof}[1][Dowód. ]{\noindent\textsc{#1}}
{\nolinebreak[4]\hfill$\blacksquare$\\\par}
\newenvironment{sol}[1][Rozwiązanie. ]{
\noindent\textsc{#1}}
{\hfill\par}
 
\newenvironment{problem}{\noindent\textsc{Zadanie}\\}
{\hfill\par}
 
\def\deg{^{\circ}}
\def\source#1{\\Źródło: #1}
 
 
\subimport{../}{style}
%\include{style}
 
\begin{document}
\section{Fermat, Euler i inne chłopaki}
 
\subsection{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\Big|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}[Eulera]
            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}
\subsection{Zadania}
\begin{enumerate}
    \item
        \begin{problem}
            Uzasadnij (najlepiej bez obliczeń), że
            \begin{enumerate}
                \item $
                    21\Big|1^7 + 2^7 + \dots + 6^7,
                    $
                \item
                    $
                    21\Big|1^{600001} + 2^{600001} + \dots + 6^{600001}.
                    $
            \end{enumerate}
            \emph{Wskazówka: $21 = 1+2+3+4+5+6$. Hm, czyżby zachodziło jakieś
            przystawianie $\mod$ 21 ;).}
        \end{problem}
    \item
        \begin{problem}
            Udowodnij (w skończonym czasie; da się bez obliczeń), że dla
            dowolnej liczby całkowitej $a$, liczba $a^{1005}$ daje z dzielenia
            przez $2011$ resztę ze zbioru $\{-1, 0, 1\}$.
        \end{problem}
    \item
        \begin{problem}
            Udowodnij, że:
            \begin{enumerate}
                \item $7^6 \equiv 6^6 \equiv 1 \mod 43$,
                \item jeżeli $n = 6k-1$ ($k\in \mathbb{Z}$), to $43\Big|7^n - 6^n - 1$,
                \item jeżeli $n =6k+1$ ($k\in \mathbb{Z}$), to $43\Big|7^n - 6^n - 1$,
                \item jeżeli $p$ jest liczbą pierwszą większą od $3$, to
                    $43\Big|7^p - 6^p - 1$.
            \end{enumerate}
        \end{problem}
    \item \begin{problem}
            Niech $a, b$ będą względnie pierwszymi liczbami całkowitymi.
            Udowodnij, że istnieją liczby dodatnie $m, n$, takie, że
            \[
            ab\Big|a^m + b^n - 1.
            \]
        \end{problem}
    \item Udowodnij, że jeśli $p$ jest liczbą pierwszą, a $a$ jest taką liczbą
        całkowitą, że $p\Big| a^p - 1$ to
        \begin{enumerate}
            \item $p\Big|a-1$,
            \item $p^2\Big| a^p-1$.
        \end{enumerate}
    \item * Niech $a,b,c\in \mathbb{Z}$ będą takie, że $a+b+c=0$. Rozstrzygnij,
        czy $a^{61} + b^{61} + c^{61}$ może być liczbą pierwszą.
    \item ** Wyznaczyć najmniejszą taką liczbę pierwszą $p$, że liczba
        $$2^{120!}-1$$
        jest podzielna przez $p$ i nie jest podzielna przez $p^2$.
        \emph{Wskazówka: ile wynosi $\phi(p^2)?$}
\end{enumerate}
 
\end{document}