\documentclass[a4paper]{article}

\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}
\usepackage{amsfonts}

\title{Week 4: notes}



\begin{document}
\maketitle


\section{Sample detailed proofs}

\subsection{	$[3|n] \Rightarrow [3|n^2]$}

\textbf{Problem:} Prove or disprove the claim
$$
	[3|n] \Rightarrow [3|n^2]
$$

%1. Understand why the claim is true
% n=6    3|36? yes! 36 = 12*3
% n=9    3|81? yes! 81 = 27*3

\noindent $m|n$ (sometimes pronounced ``$m$ divides $n$) means that $n$ is divisible by $m$. In other words, 
$$
	[m|n] \Leftrightarrow [\exists k \in \mathbb{Z}, n = km]
$$

 \textbf{Solution:}

The claim is \textbf{true}. Proof:

\begin{enumerate}
	\item Let $k$ be an integer such that $n = 3k$ ($k$ exists since $3|n$)
    	\item Then $n^2 = 9k^2 = 3(3k^2)$ (refactoring)
    	\item $3(3k^2)$ is divisible by $3$ ($3k^2$ is an integer)
    	\item Therefore, $n^2$ is divisible $3$
\end{enumerate}


\subsection{	$[8|n^2] \Rightarrow [8|n]$}

\textbf{Problem:} Prove or disprove the claim
$$
	[8|n^2] \Rightarrow [8|n]
$$

% n = 2*2, n^2 = (2*2)*(2*2)

The claim is \textbf{false}. Proof:

Let $n =  4$. $8|4^2$ (since $4^2 = 2*8$) but $\lnot (8 | 4)$ (since 4 is a positive integer that's smaller than 8). So for $n = 4$, $[8|n^2] = T$, and $[8|n] = F$, so $[[8|n^2] \Rightarrow [8|n]] = F$.


\subsection{	$[3|n^2] \Rightarrow [3|n]$}

\textbf{Problem:} Prove or disprove the claim. For all $n \in \mathbb{N}$
$$
	[3|n^2] \Rightarrow [3|n]
$$

%12 = 2*2*3

The claim is \textbf{true}. Proof:
\begin{enumerate}
\item Let $k$ be an integer such that $n^2 = 3k$ ($k$ exists since $3|n^2$)
\item $n^2 = 3^{k_3}*p_1^{k_{p_1}}*p_2^{k_{p_2}}*....*p_m^{k_{p_m}}$, where $p_1$, $p_2$, ... $p_m$ are different prime factors of $n^2$ (every number can factorized into prime factors in a unique way)
\item $n$ has the same prime factors as $n^2$ (since $n^2 = n*n$) so $n = 3^{k_3 / 2}*q$ where $q$ is a product of prime factors of $n^2$
\item Therefore, $n$ is divisible by $3$.
\item So if we assume that $3|n^2$, we conclude that $3|n$.
\item So $[3|n^2] \Rightarrow [3|n]$
\end{enumerate}


\end{document}