برهان خلف
مثال‌ها

ثابت کنید که «ریشۀ دوم ۲، گنگ است».
این یک مثال معروف و قدیمی از اثبات با برهان خلف می‌باشد. به برهان خلف فرض کنید که  {\sqrt {2}} گنگ نباشد، یعنی گویا باشد. پس می‌توانیم آن را به‌صورت  {\sqrt {2}}={\frac {a}{b}} بنویسیم که  a و  b اعدادی صحیح هستند و  b\neq 0. همچنین  a و  b تا حد امکان ساده شده‌اند و در واقع نسبت به هم اول هستند. از  {\sqrt {2}}={\frac {a}{b}} نتیجه می‌شود:
{\sqrt {2}}={\frac {a}{b}}\Rightarrow 2={\frac {a^{2}}{b^{2}}}\Rightarrow 2b^{2}=a^{2}
از اینجا نتیجه می‌شود که  a^{2} زوج است، در نتیجه  a نیز زوج است (زیرا اگر  a فرد باشد، آنگاه  a^{2} هم فرد می‌شود). چون  a زوج است، پس به شکل  a=2k قابل نوشتن است که  k عددی صحیح است. داریم:
2b^{2}=a^{2}\Rightarrow 2b^{2}=(2k)^{2}\Rightarrow 2b^{2}=4k^{2}\Rightarrow b^{2}=2k^{2}
از اینجا نتیجه می‌شود که  b^{2} زوج است، در نتیجه  b نیز زوج است. از آنجایی که  a و  b هر دو اعدادی زوج هستند، پس ساده می‌شوند و نسبت به هم اول نیستند، اما این در تناقض با فرض ماست که فرض کرده بودیم که  a و  b نسبت به هم اول هستند. پس فرض خلف باطل شد و در نتیجه  {\sqrt {2}} گنگ است.  \blacksquare
ثابت کنید که «تعداد اعداد اول، نامتناهی است».
قضیۀ اقلیدس بیان می‌کند که «تعداد اعداد اول، نامتناهی است». در اصول اقلیدس، این قضیه در کتاب نهم، گزارۀ 20 بیان شده‌است. به برهان خلف فرض کنید که تعداد اعداد اول، نامتناهی نباشد. یعنی متناهی و محدود باشد و تنها  n عدد اول به شکل  p_{1},\ldots ,p_{n} داشته باشیم. حاصل‌ضرب این  n عدد اول را  P می‌نامیم:
P=p_{1}\cdot \ldots \cdot p_{n}
سپس حاصل‌جمع آن‌ها با یک را  Q می‌نامیم:  Q=P+1. چون  Q از همۀ اعداد اول  p_{1} تا  p_{n} بزرگ‌تر است، پس طبق فرض خلف،  Q نمی‌تواند اول باشد. در نتیجه مرکب است. از آنجایی که هر عدد مرکب حداقل یک شمارندۀ اول دارد، پس  Q باید بر یکی از اعداد اول p_{1} تا  p_{n} بخش‌پذیر باشد. این عدد را  p_{i} در نظر بگیرید. پس هم  P و هم  Q بر  p_{i} بخش‌پذیر هستند. در نتیجه تفاضل آن‌ها یعنی  Q-P نیز بر  p_{i} بخش‌پذیر است. اما این ممکن نیست؛ زیرا  Q-P برابر با یک است و عدد یک بر هیچ عدد اولی بخش‌پذیر نیست. پس فرض خلف باطل شد و در نتیجه تعداد اعداد اول، نامتناهی است.  \blacksquare
ثابت کنید که «تجزیۀ هر عدد طبیعی به عوامل اول، صرف نظر از ترتیب عوامل یکتا است».
یکی از قضایای مهم در نظریۀ اعداد، قضیۀ اساسی حساب است که بیان می‌کند که «هر عدد طبیعی بزرگ‌تر از یک را می‌توان به شکل ضرب یک یا چند عدد اول نمایش داد و این تجزیه صرف نظر از ترتیب عوامل، یکتا است». یکتا بودن تجزیه به عوامل اول را می‌توان با برهان خلف ثابت کرد. فرض کنید که  s کوچک‌ترین عدد صحیح مثبتی است که که به دو صورت مختلف به اعداد اول تجزیه می‌شود. پس می‌نویسیم:
{\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}\end{aligned}}
که  p_{1} تا  p_{m} و  q_{1} تا  q_{n} اعدادی اول هستند. همچنین هر  p_{i} باید از هر  q_{j} متمایز باشد؛ زیرا در غیر این صورت اگر مثلاً  p_{i}=q_{j}، آنگاه:
t={\frac {s}{p_{i}}}={\frac {s}{q_{j}}}
که یعنی عددی مانند  t وجود دارد که کوچک‌تر از  s است و دو تجزیۀ متفاوت دارد، در حالی که چنین نیست و طبق فرض خلف،  s کوچک‌ترین عددی که که به دو صورت مختلف به اعداد اول تجزیه می‌شود. پس برای هر  i از یک تا  m و هر  j از یک تا  n، داریم:  p_{i}\neq q_{j}. پس بدون آسیب به کلیت مسئله، فرض کنید که  p_{1}<q_{1}. سپس تعریف می‌کنیم:
P=p_{2}\cdots p_{m},\ Q=q_{2}\cdots q_{n}
در نتیجه داریم:  s=p_{1}P=q_{1}Q. سپس می‌نویسیم:
\left.{\begin{array}{l}s-p_{1}Q=q_{1}Q-p_{1}Q=(q_{1}-p_{1})Q\\s-p_{1}Q=p_{1}P-p_{1}Q=(P-Q)p_{1}\end{array}}\right\rbrace \Longrightarrow (q_{1}-p_{1})Q=(P-Q)p_{1}
همچنین هر دوی  (q_{1}-p_{1})Q و  (P-Q)p_{1}، چون برابر با  s-p_{1}Q هستند، در نتیجه از  s کوچک‌تر می‌باشند و از آنجایی که هر عدد کوچک‌تر از  s، تجزیۀ یکتا دارد، پس هر دوی  (q_{1}-p_{1})Q و  (P-Q)p_{1} دارای تجزیۀ یکتا هستند و چون با هم برابرند، در نتیجه هر عاملی که در  (P-Q)p_{1} می‌باشد، باید در  (q_{1}-p_{1})Q هم باشد. بنابراین  p_{1} باید یا در تجزیۀ  Q وجود داشته باشد و یا در تجزیۀ  (q_{1}-p_{1}). اما هر دو حالت غیرممکن هستند؛ زیرا نشان دادیم که برای هر  i از یک تا  m و هر  j از یک تا  n، داریم  p_{i}\neq q_{j}، پس  p_{1} در تجزیۀ  Q نمی‌تواند وجود داشته باشد و اگر در تجزیۀ  (q_{1}-p_{1}) باشد، آنگاه داریم:
p_{1}\mid (q_{1}-p_{1})\Rightarrow q_{1}-p_{1}=p_{1}k\ \ (k\in \mathbb {Z} )\Rightarrow q_{1}=p_{1}k+p_{1}=p_{1}(k+1)\Rightarrow p_{1}\mid q_{1}
که یعنی  q_{1} بر  p_{1} بخش‌پذیر است، اما از آنجایی که  q_{1} و  p_{1} هر دو اعدادی اول و متمایز هستند، چنین چیزی غیرممکن می‌باشد. پس فرض خلف باطل شد و در نتیجه تجزیۀ هر عدد طبیعی به اعداد اول، صرف نظر از ترتیب عوامل یکتا است.  \blacksquare