% File: numeri.tex % Created: Sat Mar 3 09:01:40 CET 2007 % Last Change: Sat Oct 07 10:00 AM 2006 C % % % (c) Copyright 2007 Andrea Lo Pumo aka AlpT % % This source code is free software; you can redistribute it and/or % modify it under the terms of the GNU General Public License as published % by the Free Software Foundation; either version 2 of the License, % or (at your option) any later version. % % This source code is distributed in the hope that it will be useful, % but WITHOUT ANY WARRANTY; without even the implied warranty of % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. % Please refer to the GNU Public License for more details. % % You should have received a copy of the GNU Public License along with % this source code; if not, write to: % Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. % \documentclass[a4paper]{article} \usepackage{prova} \usepackage{color,graphicx} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{amsfonts} %\usepackage{txfonts} \usepackage{xypic} \RequirePackage{ifpdf} % running on pdfTeX? \ifpdf \usepackage[pdftex,bookmarks=true, bookmarksnumbered=false, bookmarksopen=false, colorlinks=true, linkcolor=webred] {hyperref} \definecolor{webgreen}{rgb}{0, 0.5, 0} % less intense green \definecolor{webblue}{rgb}{0, 0, 0.5} % less intense blue \definecolor{webred}{rgb}{0.5, 0, 0} % less intense red \fi \newtheorem{thm}{Theorem}[section] \newtheorem{cor}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem{ax}{Axiom} \theoremstyle{definition} \newtheorem{defn}{Definition}[section] \theoremstyle{remark} \newtheorem{rem}{Remark}[section] \newtheorem*{notation}{Notation} \newcommand{\I}{\mathcal{I}} \newcommand{\qq}{\qquad} \newcommand{\Oo}{\overline} \newcommand{\T}[1]{\textrm{#1}} \newcommand{\legendre}[2]{\left(\frac{#1}{#2}\right)} \title{Teoria dei Numeri} \author{AlpT (@freaknet.org)} \begin{document} \pagenumbering{roman} \maketitle{} \pagebreak \begin{small} Copyright \copyright 2007 Andrea Lo Pumo aka AlpT $<$alpt@freaknet.org$>$. All rights reserved. This document is free; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This document is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE\@. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this document; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. \end{small} \clearpage \tableofcontents \clearpage \pagenumbering{arabic} \section{Anelli Noetheriani} Un anello si dice Noetheriano se vale una delle seguenti condizioni: \begin{enumerate} \item Vale la c.c.a.f per gli ideali, cioe' la seguente catena \[ I_1 \subseteq I_2 \subseteq \dots \] si stabilizza. Ovvero, a partire da un certo punto in poi, tutti gli ideali sono uguali. \item Ogni famiglia di ideali ammette l'elemento massimale \item Ogni ideale dell'anello e' finitamente generato \end{enumerate} \step{}{Dimostriamo $1\Rightarrow 2$ } \begin{prova} \assume{ $X$ poset, non vuoto, in cui vale la c.c.a.f } \prove{ Esiste $y_n\in X:\;y_n$ e' massimale } \pf \pflet{$Y_1\subseteq X,\;Y_1\neq \emptyset\;\;\;y_1\in Y_1$} \case{ $y_1$ e' massimale }~\qed \case{ $y_1$ non e' massimale } \begin{align*} & \exists Y_2 \subseteq X,\; Y_2 \neq \emptyset\;\;\;y_2\in Y_2\\ & y_2 > y_1 \end{align*} \case{ $y_2$ e' massimale }~\qed \case{ $y_2$ non e' massimale } \dots Procedendo in questa maniera formiamo la seguente catena: \[ y_1n$, sono tali che $y_m=y_n$. \qed \end{prova} \begin{thm} Il teorema della base di Hilbert afferma che: \[ A\equiv \textrm{ Noeth}\;\Rightarrow \;A[x]\equiv \textrm{ Noeth} \] Come corollario, dato il campo $K$: \[ K\equiv \textrm{ Noeth}\;\Rightarrow \;K[x]\equiv \textrm{ Noeth}\;\Rightarrow \;K[x,y]\equiv \textrm{ Noeth}\;\Rightarrow \;\dots \] \end{thm} \subsection{Proprieta'} \begin{enumerate} \item $A$ anello Noetheriano e' un UFD se vale la seguente proprieta': \[ \forall a \in A,\; a\equiv \textrm{ irriducibile}\;\Rightarrow \;a\equiv \textrm{ primo} \] Questa e' un immediata conseguenza della caratterizzazione degli UFD. \item $PID \Rightarrow Noeth$\\ Infatti, ogni PID e' finitamente generato. \end{enumerate} \section{Residuo quadratico} Sia $p\neq 2$ primo, e sia $a\in Z_p^*$ \[ x^2=a\;\;(\mathbb{Z}_p) \] distinguiamo due casi: \case{ Ammette soluzione $\pm x_0$ } preso $y\in \mathbb{Z}_p^*\setminus\{\pm x_o\}$ l'equazione $yy'=a$, dove $y'$ e' l'incognita, ammette sempre soluzione ($\mathbb{Z}_p$ e' un campo). L'insieme $ \mathbb{Z}_p^*\setminus\{\pm x_o\}$ e' formato da $p-3$ elementi, quindi esistono $\frac{p-3}{2}$ coppie $yy'$ tali che $yy'=a$. Allora se moltiplichiamo tutte le coppie tra loro otteniamo $a^{\frac{p-3}{2}}$. Riassumendo tutto quello che abbiamo trovato: \\ \[ \prod_{x\in\mathbb{Z}_p^*} x = -x_0^2a^{\frac{p-3}{2}} = -a^{\frac{p-1}{2}} \] In questo caso diremo che $a$ e' un residuo quadratico modulo $p$, e utilizzeremo il simbolo di Legendre: \[ \legendre{a}{p}=1 \] \case{ Non ammette soluzione } In questo caso, per ogni $y\in \mathbb{Z}_p^*$ esiste un $y':\;yy'=a$, quindi esistono $\frac{p-1}{2}$ coppie $yy'$, e moltiplicandole tutte tra loro otteniamo: \[ \prod_{x\in\mathbb{Z}_p^*} x = a^{\frac{p-1}{2}} \] In questo caso diremo che $a$ non e' un residuo quadratico modulo $p$. \[ \legendre{a}{p}=-1 \] \subsection{Simbolo di Legendre} Come abbiamo visto prima: \[ \legendre{a}{p}=\begin{cases} 1 & \textrm{ $a$ e' un residuo quadratico modulo $p$}\\ -1&\textrm{ se non lo e'} \end{cases} \] Una formula (non ottimale) per calcolare il simbolo di Legendre e': \[ \legendre{a}{p} = a^{\frac{p-1}{2}} \] Nota: siamo sempre in $\mathbb{Z}_p$ \begin{prova} \case{ $a$ e' un residuo quadratico modulo $p$} come abbiamo visto prima: \[ \prod_{x\in\mathbb{Z}_p^*} x = -a^{\frac{p-1}{2}} \] ma e' anche vero che \[ \prod_{x\in\mathbb{Z}_p^*} x = (p-1)! = -1\;\;\textrm{ [thm di Wilson]} \] quindi \[ -a^{\frac{p-1}{2}} = -1\;\Rightarrow \;a^{\frac{p-1}{2}} = 1 = \legendre{a}{p} \] \case{ $a$ non e' un residuo quadratico modulo $p$ } procedendo come prima arriviamo a: \[ a^{\frac{p-1}{2}} = -1 = \legendre{a}{p} \] \qed \end{prova} \section{Somma di quadrati} \label{lalala} $x^2+1=0$ ha soluzioni in $Z_p\;\Leftrightarrow \;$ $p=4k+1$ \step{}{Dim. $\Leftrightarrow$ } \begin{prova} \begin{align*} & x^2+1=0 \;\Leftrightarrow \; \legendre{-1}{p}=1\;\Leftrightarrow \;{(-1)}^{\frac{p-1}{2}} = 1 \\ & {(-1)}^{\frac{p-1}{2}} = 1 \;\Leftrightarrow \;\frac{p-1}{2}=2k,\;k\in \mathbb{Z}\\ &p-1=4k \end{align*} \qed \end{prova} Questo e' una dimostrazione alternativa (e molto piu' elegante) a quella usata in un passo del paragrafo ``somma di quadrati'' che negli appunti di Algebra I:\\ \verb|fenix.olocolors.org/~alpt/appunti/algebraI/algebraI.pdf|\\ Dato $n\in\mathbb{Z}$, e la sua fattorizzazione \[ n=2^tq_1^{m_1}q_2^{m_2}\dots q_r^{m_r}p_1^{n_1}p_2^{n_2}\dots p_s^{n_s}\] dove \[ t\ge 0,\;\;\forall i\;q_i=1\;(\mathbb{Z}_4),\;\;p_i=3\;(\mathbb{Z}_4) \] allora \[ n=a^2+b^2\;\Leftrightarrow \;\forall i,\;n_i\in 2\mathbb{N} \] \step{}{Dimostriamo solo $\Rightarrow $, dato che la dimostrazione per $\Leftarrow $ e' stata gia' fatta negli appunti di Algebra I} \begin{prova} \assume{ \begin{enumerate} \item $n=a^2+b^2$ \item $n=2^tq_1^{m_1}q_2^{m_2}\dots q_r^{m_r}p_1^{n_1}p_2^{n_2}\dots p_s^{n_s}$ \item $t\ge 0,\;\;\forall i\;q_i=1\;(\mathbb{Z}_4),\;\;p_i=3\;(\mathbb{Z}_4)$ \end{enumerate} } \prove{ $n_i\in 2\mathbb{N}$ }\pf \pflet{ $d=MCD(a,b)$ } \begin{align*} & d/a\;\Rightarrow \;a=\lambda d\;\Rightarrow \;a^2=\lambda^2 d^2\;\Rightarrow d^2/a^2\\ & d/b\;\Rightarrow \;b=\mu d\;\Rightarrow \;b^2=\mu^2 d^2\;\Rightarrow d^2/b^2\\ & d^2/a^2,\;d^2/b^2\;\Rightarrow \;d^2/n\\ & n=d^2m\\ & \frac{n}{d^2}=m=\frac{a^2}{d^2}+\frac{a^2}{d^2}=\lambda^2+\mu^2 \end{align*} \assume{$p=4h+3:\;\;p/d$ } \step{}{Dimostreremo che $p$ compare con esponente pari nella decomposizione di $n$ facendo vedere che $p\nmid m$} \begin{prova} \assume{ Per assurdo $p/m$ } \prove{ assurdo } \pf Come abbiamo visto prima, $m=\lambda^2+\mu^2$, con $MCD(\lambda, \mu)=1$.\\ Allora, \begin{align*} & p/m\;\Leftrightarrow \;m=\lambda^2+\mu^2=0\;(\mathbb{Z}_p) \end{align*} Poiche' $(\lambda, \mu)=1$, $p$ non puo' dividere contemporaneamente $\lambda$ e $\mu$, e inoltre non puo' neanche dividerne uno solo, infatti, se supponiamo per assurdo che divide $\lambda$ abbiamo: \begin{align*} & \lambda^2+\mu^2=\mu^2=0\;(\mathbb{Z}_p) \end{align*} e quindi dividerebbe anche $\mu$, che e' assurdo perche' $(\lambda, \mu)=1$. Quindi $\lambda,\mu\neq 0\;\;(\mathbb{Z}_p$. Poiche' $\mathbb{Z}_p$ e' un campo, $\exists c:\;\;\mu=\lambda c$. Sostituendo la $b$: \[ \lambda^2+\mu^2=\lambda^2+(\lambda^2 c^2)=\lambda^2(1+c^2)=0\;\;(\mathbb{Z}_p) \] e poiche' $\lambda\neq 0$, ci riduciamo a \[ 1+c^2=0\;\;(\mathbb{Z}_p) \] ma questo e' assurdo, perche' $c^2=-1$ ammette soluzione se e solo se $p$ e' della forma $4k+1$ (lo abbiamo dim. al paragrafo \ref{lalala}) \qed \end{prova} \qed \end{prova} \begin{thm} Un numero $n$ e' somma di tre quadrati se e solo se non e' del tipo $4^n(8k+7)$ \end{thm} \begin{thm} Ogni numero intero e' somma di 4 quadrati. \end{thm} \begin{thm} Ogni numero e' somma di 9 cubi.\\ In realta', escludendo solo $23$ e $239$, tutti gli altri interi si possono scrivere come somma di $8$ cubi. \end{thm} \begin{thm} Indichiamo con $G(3)$ il numero di cubi necessari a scrivere tutti i numeri interi positivi, tranne un insieme finito di essi, come somma di cubi. Esiste questo teorema: \[ 4\le G(3)\le 7 \] \end{thm} \section{Primi in $\mathbb{Z}[i]$} \begin{prop} \[ \pi\in\mathbb{Z}[i]\textrm{ primo}\;\Rightarrow \;\exists z\in \mathbb{Z}:\;\;\pi/z \] \end{prop} \begin{prova}\pf \[ |\pi|=\pi\Oo{\pi}=n\in\mathbb{Z}\;\Rightarrow \;\pi/n \] \qed \end{prova} \begin{prop} Dato $\pi\in\mathbb{Z}[i]$ \[ |\pi|\textrm{ primo}\;\Rightarrow \;\pi\textrm{ primo} \] \end{prop} \begin{prova}\pf Per assurdo $\pi=\lambda \mu$ con $\lambda,\mu$ non invertibili. \[ |\pi|=|\lambda| |\mu| \] ma $|\pi|$ e' primo e quindi irriducibile, e quindi o $|\lambda|$ o $ |\mu|$ e' un invertibile. Supponiamo che lo sia $|\lambda|$, cioe' $|\lambda|=1$, ma questo implicherebbe che $\lambda$ stesso e' un invertibile in $\mathbb{Z}[i]$ il che' e' un assurdo contro ipotesi. \qed \end{prova} \begin{prop} Dato un $p\in\mathbb{Z}$ analizziamo 3 casi: \begin{enumerate} \item $p=2$:\\ \[ 2=1^2+1^2=(1+i)(1-i)=-i(1+i)^2 \] Si dice che $2$ e' ramificato.\\ $(1+i)$ e' primo in $\mathbb{Z}[i]$. \item $p=4k+1$:\\ \[ p=a^2+b^2=(a+ib)(a-ib) \] $a+ib$, $a-ib$ e' una coppia di primi coniugati in $\mathbb{Z}[i]$.\\ Si dice che $p$ e' decomposto. \item $p=4h+3$:\\ $p$ resta primo in $\mathbb{Z}[i]$.\\ Si dice che $p$ e' inerte. \end{enumerate} \end{prop} \section{Primi infiniti} \begin{prop} Esistono infiniti primi della forma $4k+3$. \end{prop} \begin{prova} \assume{ Per assurdo che $A=\{p_1,\dots,p_n\}$ sia l'insieme finito dei primi $4k+3$. } \pf Consideriamo il numero $q=4p_1\cdot p_2\cdot p_3\cdot\dots\cdot p_n+3$ e consideriamo la sua fattorizzazione: $q=q_1q_2\dots q_t$. Poiche' prodotti di numeri congrui 1 modulo 4 sono chiusi rispetto al prodotto\[(4k+1)(4h+1)=4(5h+k)+1\] deve esistere almeno un $q_i$ congruo 3 modulo 4 per fare in modo che $q$ sia pure congruo 3 (lo e' per costruzione). Se $q_i \in A$, cioe' se $q_i=p_j$, avremmo: \[ q_i/q,\;\;q/4p_1\cdot p_2\cdot p_3\cdot\dots\cdot p_n\;\Rightarrow \;q_i/3 \] Il che e' impossibile, quindi $q_i\notin A$, ma allora abbiamo trovato un primo della forma $4k+3$ che non appartiene in $A$, ed ecco l'assurdo. \qed \end{prova} \begin{prop} Esistono infiniti primi della forma $4k+1$. \end{prop} \begin{prova} \assume{ Per assurdo che $A=\{p_1,\dots,p_n\}$ sia l'insieme finito dei primi $4k+1$. }\pflet{ \begin{enumerate} \item $B=\{3,5,7,\dots,p\}$ in modo tale che $A\subseteq B$ \item $n=3^25^27^2\dots p^2+2^2$ \end{enumerate} } $n$ e' somma di quadrati e' quindi e' della forma $4k+1$, allora tutti i suoi fattori primi sono pure nella forma $4k+1$, perche' prodotti di numeri congrui 1 modulo 4 sono chiusi rispetto al prodotto: \[ (4k+1)(4h+1)=4(5h+k)+1 \] Se un $p_i\in A$ fosse un fattore di $n$ avremmo che: \[ p_i/n,\;p_i/3^25^27^2\dots p^2\;\Rightarrow \;p_i/2^2 \] il che e' impossibile, quindi ogni fattore primo di $n$ deve essere della forma $4k+1$ ma non deve appartenere ad $A$. Assurdo. \qed \end{prova} \begin{thm} Teorema di Dirichlet.\\ \[ MCD(a,b)=1\;\Rightarrow \;\{ak+b\;|\;k\in \mathbb{Z}\} \textrm{ contiene infiniti primi} \] \end{thm} \begin{thm} Teorema dei numeri primi.\\ \[ \pi(x)\approx\frac{x}{\log x}\;\;\Leftrightarrow \;\;\lim_{x\to \infty} \frac{\pi(x)}{\frac{x}{\log x}}=1 \] dove $\pi(x)$ e' il numero di primi minori o uguali a $x$.\\ \end{thm} \section{Riemman} Questa e' la famosa funzione di Riemman: \[ \zeta(s)=\sum_{n=1}^\infty \frac{1}{n^s} \] per $s>1$ converge.\\ Questa funzione puo' anche essere definita $\forall s \in \mathbb{C}$.\\ L'Ipotesi di Riemann afferma che tutti gli zeri di questa funzione si trovano in \[\left\{\frac{1}{2}+iy,\;y\in\mathbb{R}\right\}\] Eulero ha dimostrato che \[ \zeta(s)=\prod_p \frac{1}{1-\frac{1}{p^s}} \] \section{Reciprocita' quadratica} Il simbolo di Legendre $\legendre{d}{p}$ con $p\nmid a$ si puo' interpretare come la seguente composizione di omomorfismi: \[ \mathbb{Z}\setminus p\mathbb{Z}\longrightarrow \mathbb{Z}_p^*\longrightarrow \frac{\mathbb{Z}_p^*}{({\mathbb{Z}_p^*})^2} \] dove $({\mathbb{Z}_p^*})^2$ e' l'insieme dei elementi quadrati in $\mathbb{Z}_p$.\\ $\frac{\mathbb{Z}_p^*}{({\mathbb{Z}_p^*})^2}=\{1,-1\}$, proprio perche' un elemento in $\mathbb{Z}_p^*$ puo' essere o un quadrato, e quindi diventa equivalente a $1$ oppure non esserlo, e quindi diventa equivalente a $-1$.\\ Da queste osservazioni seguono queste due proprieta': \begin{enumerate} \item $d=d'\;\;(\mathbb{Z}_p)\;\Rightarrow \;\legendre{d}{p}=\legendre{d'}{p}$. Ovviamente se $d$ e' uguale a $d'$, allora avranno lo stesso simbolo di Legendre. \item $\legendre{dd'}{p}=\legendre{d}{p}\legendre{d'}{p}$. Questo proprio perche' $\legendre{d}{p}$ e' un omomorfismo. \end{enumerate} \subsection{Teorema di reciprocita' di Gauss} Dati $p,q$ primi dispari \[ \legendre{p}{q}\legendre{q}{p} = {(-1)}^{p'q'}\;\;\;p'=\frac{p-1}{2},\;q'=\frac{q-1}{2} \] Possiamo usare questo teorema per calcolare velocemente il simbolo di Lagrange.\\ Ecco un esempio: vogliamo calcolare $\legendre{13}{29}$, per gauss: $\legendre{13}{29}\legendre{29}{13}=(-1)^{6*14}=1$ allora abbiamo due casi: $\legendre{13}{29}=\legendre{29}{13}=\pm 1$\\ consideriamo $\legendre{29}{13}$ che e' uguale a $\legendre{3}{13}$ perche' $29=3\;\;(\mathbb{Z}_{13})$. \\Reiteriamo: $\legendre{3}{13}\legendre{13}{3}=(-1)^{2*6}=1$\\ allora abbiamo due casi: $\legendre{3}{13}=\legendre{13}{3}=\pm 1$\\ consideriamo $\legendre{13}{3}=\legendre{1}{3}=1$. Quindi poiche' $\legendre{13}{3}=1$ e poiche' $\legendre{3}{13}\legendre{13}{3}=1$ deduciamo che $\legendre{3}{13}=1$. Ma poiche' prima avevamo visto che $\legendre{29}{13}=\legendre{3}{13}=1$, e poiche' $\legendre{13}{29}\legendre{29}{13}=1$, concludiamo che $\legendre{13}{29}=1$ \end{document}