Art of Problem Solving

AoPS Online

User:Temperal/The Problem Solver's Resource6

< User:Temperal

Revision as of 18:19, 10 January 2009 by Temperal (talk | contribs) (rmv)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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\ne{p}$ , $a^{p-1}\equiv 1 \pmod{p}$ .

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

Gauss's Theorem

If $a|bc$ and $(a,b) = 1$ , then $a|c$ .

Errata

All quadratic residues are $0$ or $1\pmod{4}$ and $0$ , $1$ , or $4$ $\pmod{8}$ .

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

© 2024 AoPS Incorporated