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"

(→‎Euler's Phi Theorem)
(→‎Errata)
Line 46: Line 46:
 
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.
 
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.
  
−
===Errata===
+
===Quadratic Residues===
 
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>.
 
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>.
−
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.
+
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 4====
 +
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)
 +
 
 +
=====Solution=====
 +
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.
  
 
[[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]]

Revision as of 22:11, 10 January 2009

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

Number Theory

This section covers number theory, specifically Fermat's Little Theorem, Wilson's Theorem, and Euler's Totient Theorem.

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}$

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 4

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.

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=29399"