The number being divided into another number. Ex. b|d b is the divisor

Greatest Common Divsior

The largest factor in common between 2 or more given numbers. gcd(a,b) is the positive integer d satisfying d|a and d|b. If c|a and c|b then c is less than or equal to do

Least common multiple

Smallest positive number that is evenly divisible by 2 or more given numbers. The lcm (a,b) is the positive integer satisfying a|m and b|m. If a|c and b|c then c is greater than or equal to m

Two or more numbers are relatively prime if and only if their gcd is 1

Any number who's only factors are 1 and itself

Any number that has more than 2 factors

If a and b are integers, we say a is equivalent to b mod n if n|(a-b)

If n is composite such that a^n = a(mod n) then n is pseudoprime to base a

A composite number n, that satisfies a^n = a(mod n) for all n. A psuedoprime that works for any mod(n)

The division algorithm

Ay integer a can be divided by a positive integer b so the remainder r is smaller than b. Ex. 3|b r = 3k, 3k+1, 3k+2

The Euclidean algorithm

An algorithm to compute the gcd(a,b), using modular arithmetic and back substitution

The fundamental theorem of arithmetic

Every positive integer n>1 is either prime or a product of primes

The Chinese remainder theorem

nk positive integers that are pairwise relatively prime, then x = a1(mod n1), x = a2(mod n2).. x = ak(modnk), has a unique solution (mod n1n2...nk)

Fermat's little theorem

P is a prime and a an integer such that p does not divide a, then a^p-1 = 1(mod p)

Any integer n>1 is prime iff (n-1)! = -1(mod n)

Use mod 16 and do Euclidean algorithm

1's and 0's using coefficients of powers of 2

last digit*16^0, + next digit*16^1...

Mathematical induction

Assume P(n) is true, show P(1) is true, then by assuming P(n) is true, show P(n+1) is true

ax+by = c with solutions x = x0+(b/d)t and y = y0 -(a/d)t

Binary exponentiation algorithm

Write k(am...a0)base 2 to write k as sums of powers of 2 and compute repeated squares of form a^2^m

Help

Options

focusNode

Didn't know it?
click below

Knew it?
click below

Don't Know

Remaining cards (0)

Know

retry

shuffle

restart

0:00

Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

Normal Size Small Size show me how

Number Theory Terms

Terms and Definitions for Number Theory exam 1

Term	Definition
Divisor	The number being divided into another number. Ex. b\|d b is the divisor
Greatest Common Divsior	The largest factor in common between 2 or more given numbers. gcd(a,b) is the positive integer d satisfying d\|a and d\|b. If c\|a and c\|b then c is less than or equal to do
Least common multiple	Smallest positive number that is evenly divisible by 2 or more given numbers. The lcm (a,b) is the positive integer satisfying a\|m and b\|m. If a\|c and b\|c then c is greater than or equal to m
Relatively prime	Two or more numbers are relatively prime if and only if their gcd is 1
Prime	Any number who's only factors are 1 and itself
Composite	Any number that has more than 2 factors
Congruence modulo n	If a and b are integers, we say a is equivalent to b mod n if n\|(a-b)
Psuedoprime base a	If n is composite such that a^n = a(mod n) then n is pseudoprime to base a
Carmichael number	A composite number n, that satisfies a^n = a(mod n) for all n. A psuedoprime that works for any mod(n)
The division algorithm	Ay integer a can be divided by a positive integer b so the remainder r is smaller than b. Ex. 3\|b r = 3k, 3k+1, 3k+2
The Euclidean algorithm	An algorithm to compute the gcd(a,b), using modular arithmetic and back substitution
The fundamental theorem of arithmetic	Every positive integer n>1 is either prime or a product of primes
The Chinese remainder theorem	nk positive integers that are pairwise relatively prime, then x = a1(mod n1), x = a2(mod n2).. x = ak(modnk), has a unique solution (mod n1n2...nk)
Fermat's little theorem	P is a prime and a an integer such that p does not divide a, then a^p-1 = 1(mod p)
Wilson's Theorem	Any integer n>1 is prime iff (n-1)! = -1(mod n)
Linear congruence	a1x1 + a2x2+...anxn = b(modn)
Base 16	Use mod 16 and do Euclidean algorithm
Binary	1's and 0's using coefficients of powers of 2
Base 10	last digit16^0, + next digit16^1...
Mathematical induction	Assume P(n) is true, show P(1) is true, then by assuming P(n) is true, show P(n+1) is true
Diophantine Equation	ax+by = c with solutions x = x0+(b/d)t and y = y0 -(a/d)t
Binary exponentiation algorithm	Write k(am...a0)base 2 to write k as sums of powers of 2 and compute repeated squares of form a^2^m

Created by: slpause

"Know" box contains:
Time elapsed:
Retries: