Difference between revisions of "User:Temperal/The Problem Solver's Resource6"
(→Number Theory) |
(→Number Theory) |
||
Line 1: | Line 1: | ||
__NOTOC__ | __NOTOC__ | ||
{{User:Temperal/testtemplate|page 6}} | {{User:Temperal/testtemplate|page 6}} | ||
− | ==<span style="font-size:20px; color: blue;">Number Theory</span>== | + | ==<span style="font-size:20px; color: blue;">Beginner Number Theory</span>== |
This section covers [[number theory]], specifically [[Fermat's Little Theorem]], [[Wilson's Theorem]],[[Euler's Totient Theorem]], and [[Quadratic residues]]. | This section covers [[number theory]], specifically [[Fermat's Little Theorem]], [[Wilson's Theorem]],[[Euler's Totient Theorem]], and [[Quadratic residues]]. | ||
Revision as of 22:18, 10 January 2009
Introduction | Other Tips and Tricks | Methods of Proof | You are currently viewing page 6. |
Beginner Number Theory
This section covers number theory, specifically Fermat's Little Theorem, Wilson's Theorem,Euler's Totient Theorem, and Quadratic residues.
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
.
is the greek letter phi.
is the number of integers less than or equal to m that are at the same time relatively prime to n. If the prime factorization of n is
,
.
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 Problem 1
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 ,
.
Example Problem 2
Let be an integer such that
. Find the remainder when
is divided by
.
Solution
After multiplying through by , we know that every term on the left-hand-side will be divisible by 13 except for
. We wish to find the remainder when
is divided by 13. From Wilson's Theorem, we know that
so we consider (mod 13). Thus, the remainder is
which comes out to be 7. Thus, our answer is 7.
Euler's Phi Theorem
If , then
, where
is the number of relatively prime numbers lower than
. This is mostly a generalization of Fermat's Little Theorem, although much more useful.
Quadratic Residues
An integer n is a quadratic residue (mod m) if and only if there exists an integer p such that .
Some useful facts are that all quadratic residues are
or
and
,
, or
. All cubic residues (mod 9) are 0, 1, or -1.
Example Problem 3
Does there exist an integer such that its cube is equal to , where n is an integer? (IMO longlist 1967)
Solution
Consider (mod 9), and n (mod 3). If n is divisible by 3,
is clearly divisible by 9. If n is congruent to 1 (mod 3),
is congruent to 6 (mod 9). If n is congruent to 2 (mod 3), then
. As n+1 is divisible by 3, it is congruent to 0 (mod 9). Hence,
is either 7 or 4 (mod 9). However, all cubes are 0,1, or -1 (mod 9), so there does not exist such an integer.