Difference between revisions of "User:Temperal/The Problem Solver's Resource6"
(→Errata) |
|||
Line 38: | Line 38: | ||
===Errata=== | ===Errata=== | ||
− | 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>. | + | 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. | ||
[[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 20:13, 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
if
is the remainder when
is divided by
to give an integral amount. Also, this means b divides (n-a).
(or
divides
) if
for some integer
.
Special Notation
Occasionally, if two equivalent expressions are both modulated by the same number, the entire equation will be followed by the modulo.
refers to the greatest common factor of
and
refers to the lowest common multiple of
.
Properties
For any number there will be only one congruent number modulo between
and
.
If and
, then
.
Fermat's Little Theorem
For a prime and a number
such that
,
. A frequently used result of this is
.
Example: Find all primes p such that .
Solution: Firstly, p=2 clearly does not work. Now, as all other primes are odd, and hence
. After adding one, we have
since p divides
. However, that means p must divide 3, so the only prime possible is 3. Indeed,
is a multiple of 3.
Wilson's Theorem
For a prime ,
.
Fermat-Euler Identitity
If , then
, where
is the number of relatively prime numbers lower than
.
Errata
An integer n is a quadratic residue (mod m) if and only if there exists an integer p such that .
All quadratic residues are
or
and
,
, or
. All cubic residues (mod 9) are 0, 1, or -1.