Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "User:Temperal/The Problem Solver's Resource6"

(→‎Number Theory)
 
(20 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
__NOTOC__
 
__NOTOC__
 
{{User:Temperal/testtemplate|page 6}}
 
{{User:Temperal/testtemplate|page 6}}
−
==<span style="font-size:20px; color: blue;">Number Theory</span>==
+
==<span style="font-size:20px; color: blue;">Beginner/Intermediate Number Theory</span>==
−
This section covers [[number theory]], specifically [[Fermat's Little Theorem]], [[Wilson's Theorem]], and [[Euler's Totient Theorem]].
+
This section covers [[number theory]], specifically [[Fermat's Little Theorem]], [[Wilson's Theorem]],[[Euler's Totient Theorem]], [[Quadratic residues]], and the [[Euclidean algorithm]].
 +
 
 +
To use this page, we recommend knowing the basics of [[Linear congruence]], [[Modular arithmetic]], and have a grasp of basic number theory needed for the AMC 10 and 12.
  
 
==Definitions==
 
==Definitions==
 
*<math>n\equiv a\pmod{b}</math> if <math>n</math> is the remainder when <math>a</math> is divided by <math>b</math> to give an integral amount. Also, this means b divides (n-a).
 
*<math>n\equiv a\pmod{b}</math> if <math>n</math> is the remainder when <math>a</math> is divided by <math>b</math> to give an integral amount. Also, this means b divides (n-a).
 
*<math>a|b</math> (or <math>a</math> divides <math>b</math>) if <math>b=ka</math> for some [[integer]] <math>k</math>.
 
*<math>a|b</math> (or <math>a</math> divides <math>b</math>) if <math>b=ka</math> for some [[integer]] <math>k</math>.
 +
*<math>\phi</math> is the greek letter phi. <math>\phi(n)</math> is the number of integers less than or equal to m that are at the same time relatively prime to n. If the prime factorization of n is <math>p_1^{e_1}p_2^{e_2}...p_n^{e_n}</math>, <math>\phi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_n}\right)</math>.
  
 
==Special Notation==
 
==Special Notation==
Line 23: Line 26:
  
 
*<math>a \pmod{m} \cdot b \pmod{m} \equiv (a \cdot b) \pmod{m} </math>
 
*<math>a \pmod{m} \cdot b \pmod{m} \equiv (a \cdot b) \pmod{m} </math>
 +
 +
*<math>\frac{a}{e}\equiv \frac{b}{e}\pmod {\frac{m}{\gcd(m,e)}}</math>, where <math>e</math> is a positive integer that divides <math>{a}</math> and <math>b</math>.
 +
 +
*<math>a^e\equiv{b^e}\pmod{m}</math>
 +
 +
===Fundamental Theorem of Arithmetic===
 +
The Fundamenal Theorem of Arithmetic is fairly clear, yet is extremely important. It states that any integer n greater than one has a unique representation as a product of primes. It has a very interesting proof; attempt to prove it using contradiction.
  
 
===Fermat's Little Theorem===
 
===Fermat's Little Theorem===
Line 36: Line 46:
 
For a prime <math>p</math>, <math> (p-1)! \equiv -1 \pmod p</math>.
 
For a prime <math>p</math>, <math> (p-1)! \equiv -1 \pmod p</math>.
  
−
====Example Problem 2=====
+
====Example Problem 2====
 
Let <math>a</math> be an integer such that <math>\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{23}=\frac{a}{23!}</math>. Find the remainder when <math>a</math> is divided by <math>13</math>.
 
Let <math>a</math> be an integer such that <math>\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{23}=\frac{a}{23!}</math>. Find the remainder when <math>a</math> is divided by <math>13</math>.
  
 
=====Solution=====
 
=====Solution=====
−
After multiplying through by <math>23!</math>, we know that every term on the left-hand-side will be divisible by 13 except for <math>\frac{23!}{13}</math>. We wish to find the remainder when <math>23\cdot22\cdot21...\cdot1</math> is divided by 13. From Wilson's Theorem, we know that <math>12!\equiv-1\pmod{13}</math> so we consider (mod 13). Thus, the remainder is <math>10\cdot9\cdot8...\cdot1\cdot12!\equiv10!\cdot{-1}\pmod{13}</math> which comes out to be 6. Thus, our answer is 6.
+
After multiplying through by <math>23!</math>, we know that every term on the left-hand-side will be divisible by 13 except for <math>\frac{23!}{13}</math>. We wish to find the remainder when <math>23\cdot22\cdot21...\cdot1</math> is divided by 13. From Wilson's Theorem, we know that <math>12!\equiv-1\pmod{13}</math> so we consider (mod 13). Thus, the remainder is <math>10\cdot9\cdot8...\cdot1\cdot12!\equiv10!\cdot{-1}\pmod{13}</math> which comes out to be 7. Thus, our answer is 7.
 +
 
 +
===Euler's Phi Theorem===
 +
If <math>(a,m)=1</math>, then <math>a^{\phi{m}}\equiv1\pmod{m}</math>, where <math>\phi{m}</math> is the number of relatively prime  numbers lower than <math>m</math>. This is mostly a generalization of Fermat's Little Theorem, although much more useful.
  
−
===Fermat-Euler Identitity===
+
===Quadratic Residues===
−
If <math>gcd(a,m)=1</math>, then <math>a^{\phi{m}}\equiv1\pmod{m}</math>, where <math>\phi{m}</math> is the number of relatively prime numbers lower than <math>m</math>.
+
An integer n is a quadratic residue (mod m) if and only if there exists an integer p such that <math>p^2\equiv n\pmod{m}</math>.
 +
Some useful facts are that all quadratic residues are <math>0</math> or <math>1\pmod{4}</math> and <math>0</math>, <math>1</math>, or <math>4</math> <math>\pmod{8}</math>. All cubic residues (mod 9) are 0, 1, or -1.
  
 +
====Example Problem 3====
 +
Does there exist an integer such that its cube is equal to <math>3n^2 + 3n + 7</math>, where n is an integer? (IMO longlist 1967)
  
−
===Errata===
+
=====Solution=====
−
An integer n is a quadratic residue (mod m) if and only if there exists an integer p such that <math>p^2\equiv n\pmod{m}</math>.
+
Consider <math>3n^2 + 3n + 7</math> (mod 9), and n (mod 3). If n is divisible by 3, <math>3n^2 + 3n</math> is clearly divisible by 9. If n is congruent to 1 (mod 3), <math>3n^2 + 3n</math> is congruent to 6 (mod 9). If n is congruent to 2 (mod 3), then <math>3n^2 + 3n\equiv3(n)(n + 1)\pmod{9}</math>. As n+1 is divisible by 3, it is congruent to 0 (mod 9). Hence, <math>3n^2 + 3n + 7</math> is either 7 or 4 (mod 9). However, all cubes are 0,1, or -1 (mod 9), so there does not exist such an integer.
−
All quadratic residues are <math>0</math> or <math>1\pmod{4}</math>and  <math>0</math>, <math>1</math>, or <math>4</math> <math>\pmod{8}</math>. All cubic residues (mod 9) are 0, 1, or -1.
+
 
 +
===Solving Linear Congruences===
 +
As mentioned at the top, you should at least know how to solve simple linear congruences, with just one [[linear congruence]]. However, solving with two or more congruences is more complex, and many times there is not even a solution. The [[Chinese Remainder Theorem]] shows when the congruences do have a unique solution. *to be continued*
 +
 
 +
===Euclidean Algorithm===
  
 
[[User:Temperal/The Problem Solver's Resource5|Back to page 5]] | [[User:Temperal/The Problem Solver's Resource7|Continue to page 7]]
 
[[User:Temperal/The Problem Solver's Resource5|Back to page 5]] | [[User:Temperal/The Problem Solver's Resource7|Continue to page 7]]

Latest revision as of 11:44, 11 January 2009

Introduction | Other Tips and Tricks | Methods of Proof | You are currently viewing page 6.

Beginner/Intermediate Number Theory

This section covers number theory, specifically Fermat's Little Theorem, Wilson's Theorem,Euler's Totient Theorem, Quadratic residues, and the Euclidean algorithm.

To use this page, we recommend knowing the basics of Linear congruence, Modular arithmetic, and have a grasp of basic number theory needed for the AMC 10 and 12.

Definitions

  • $n\equiv a\pmod{b}$ if $n$ is the remainder when $a$ is divided by $b$ to give an integral amount. Also, this means b divides (n-a).
  • $a|b$ (or $a$ divides $b$) if $b=ka$ for some integer $k$.
  • $\phi$ is the greek letter phi. $\phi(n)$ is the number of integers less than or equal to m that are at the same time relatively prime to n. If the prime factorization of n is $p_1^{e_1}p_2^{e_2}...p_n^{e_n}$, $\phi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_n}\right)$.

Special Notation

Occasionally, if two equivalent expressions are both modulated by the same number, the entire equation will be followed by the modulo.

$(a_1, a_2,...a_n)$ refers to the greatest common factor of $a_1, a_2, ...a_n$ and $[a_1, a_2, ...a_n]$ refers to the lowest common multiple of $a_1, a_2,...a_n$.

Properties

For any number there will be only one congruent number modulo $m$ between $0$ and $m-1$.

If $a\equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $(a+c) \equiv (b+d) \pmod {m}$.

  • $a \pmod{m} + b \pmod{m} \equiv (a + b) \pmod{m}$
  • $a \pmod{m} - b \pmod{m} \equiv (a - b) \pmod{m}$
  • $a \pmod{m} \cdot b \pmod{m} \equiv (a \cdot b) \pmod{m}$
  • $\frac{a}{e}\equiv \frac{b}{e}\pmod {\frac{m}{\gcd(m,e)}}$, where $e$ is a positive integer that divides ${a}$ and $b$.
  • $a^e\equiv{b^e}\pmod{m}$

Fundamental Theorem of Arithmetic

The Fundamenal Theorem of Arithmetic is fairly clear, yet is extremely important. It states that any integer n greater than one has a unique representation as a product of primes. It has a very interesting proof; attempt to prove it using contradiction.

Fermat's Little Theorem

For a prime $p$ and a number $a$ such that $(a,b)=1$, $a^{p-1}\equiv 1 \pmod{p}$. A frequently used result of this is $a^p\equiv a\pmod{p}$.

Example Problem 1

Find all primes p such that $p|2^p+1$.

Solution

Firstly, p=2 clearly does not work. Now, as all other primes are odd, $(2, p)=1$ and hence $2^p\equiv2\pmod{p}$. After adding one, we have $3\equiv0\pmod{p}$ since p divides $2^p+1$. However, that means p must divide 3, so the only prime possible is 3. Indeed, $2^3+1=9$ is a multiple of 3.

Wilson's Theorem

For a prime $p$, $(p-1)! \equiv -1 \pmod p$.

Example Problem 2

Let $a$ be an integer such that $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{23}=\frac{a}{23!}$. Find the remainder when $a$ is divided by $13$.

Solution

After multiplying through by $23!$, we know that every term on the left-hand-side will be divisible by 13 except for $\frac{23!}{13}$. We wish to find the remainder when $23\cdot22\cdot21...\cdot1$ is divided by 13. From Wilson's Theorem, we know that $12!\equiv-1\pmod{13}$ so we consider (mod 13). Thus, the remainder is $10\cdot9\cdot8...\cdot1\cdot12!\equiv10!\cdot{-1}\pmod{13}$ which comes out to be 7. Thus, our answer is 7.

Euler's Phi Theorem

If $(a,m)=1$, then $a^{\phi{m}}\equiv1\pmod{m}$, where $\phi{m}$ is the number of relatively prime numbers lower than $m$. This is mostly a generalization of Fermat's Little Theorem, although much more useful.

Quadratic Residues

An integer n is a quadratic residue (mod m) if and only if there exists an integer p such that $p^2\equiv n\pmod{m}$. Some useful facts are that all quadratic residues are $0$ or $1\pmod{4}$ and $0$, $1$, or $4$ $\pmod{8}$. All cubic residues (mod 9) are 0, 1, or -1.

Example Problem 3

Does there exist an integer such that its cube is equal to $3n^2 + 3n + 7$, where n is an integer? (IMO longlist 1967)

Solution

Consider $3n^2 + 3n + 7$ (mod 9), and n (mod 3). If n is divisible by 3, $3n^2 + 3n$ is clearly divisible by 9. If n is congruent to 1 (mod 3), $3n^2 + 3n$ is congruent to 6 (mod 9). If n is congruent to 2 (mod 3), then $3n^2 + 3n\equiv3(n)(n + 1)\pmod{9}$. As n+1 is divisible by 3, it is congruent to 0 (mod 9). Hence, $3n^2 + 3n + 7$ is either 7 or 4 (mod 9). However, all cubes are 0,1, or -1 (mod 9), so there does not exist such an integer.

Solving Linear Congruences

As mentioned at the top, you should at least know how to solve simple linear congruences, with just one linear congruence. However, solving with two or more congruences is more complex, and many times there is not even a solution. The Chinese Remainder Theorem shows when the congruences do have a unique solution. *to be continued*

Euclidean Algorithm

Back to page 5 | Continue to page 7

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=User:Temperal/The_Problem_Solver%27s_Resource6&oldid=29469"