User:Temperal/The Problem Solver's Resource6

< User:Temperal
Revision as of 21:39, 10 January 2009 by Xpmath (talk | contribs) (Example Problem 2=)


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

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

Errata

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

Back to page 5 | Continue to page 7