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

Revision as of 20: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, especially modulos (moduli?).

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

Fermat-Euler Identitity

If $gcd(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

@@ Line 26: / Line 26: @@
 For a prime <math>p</math> and a number <math>a</math> such that <math>(a,b)=1</math>, <math>a^{p-1}\equiv 1 \pmod{p}</math>. A frequently used result of this is <math>a^p\equiv a\pmod{p}</math>.
-Example: Find all primes p such that <math>p|2^p+1</math>.
+====Example Problem 1====
+Find all primes p such that <math>p|2^p+1</math>.
-Solution: Firstly, p=2 clearly does not work. Now, as all other primes are odd, <math>(2, p)=1</math> and hence <math>2^p\equiv2\pmod{p}</math>. After adding one, we have <math>3\equiv0\pmod{p}</math> since p divides <math>2^p+1</math>. However, that means p must divide 3, so the only prime possible is 3. Indeed, <math>2^3+1=9</math> is a multiple of 3.
+=====Solution=====
+Firstly, p=2 clearly does not work. Now, as all other primes are odd, <math>(2, p)=1</math> and hence <math>2^p\equiv2\pmod{p}</math>. After adding one, we have <math>3\equiv0\pmod{p}</math> since p divides <math>2^p+1</math>. However, that means p must divide 3, so the only prime possible is 3. Indeed, <math>2^3+1=9</math> is a multiple of 3.
 ===Wilson's Theorem===

Page

Toolbox

Search