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

User:Temperal/The Problem Solver's Resource6

< User:Temperal
Revision as of 19:05, 10 January 2009 by Xpmath (talk | contribs) (→‎Definitions)
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}$.

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