memorisable stuff

Question 1

coprime:

Answer 1

gcd(a,b)=1, a and b are coprime, no prime factors in common

Question 2

bezout’s lemma:

Answer 2

a,b integers with at least one not equal to 0, then there’s integers s,t such that as+bt=gcd(a,b)

Question 3

some pk and qk things:

Answer 3

pkq(k-1)-p(k-1)qk=(-1)^(k-1)
pkq(k-2)-p(k-2)qk=(-1)^(k)xk
try dividing the above by the q bits for more stuff
qk>q(k-1) (and so on)

Question 4

periodic continued fractions and pell equations:

Answer 4

if root(d)=[x0: x1,…,xr] (x1-xr has a bar to show repeat), then the fundamental solution of the pell equation x^(2)-dy^(2)=1 is pn/qn where n=2r-1 if r is odd and r-1 if r is even

Question 5

unit:

Answer 5

an element of modulo n with a multiplicative inverse, so [a] is a unit modulo n if there exists [b] such that [a][b]=1, set of units is Un
[a] is a unit iff gcd(a,n)=1

Question 6

wilson’s theorem:

Answer 6

a positive int is prime iff (p-1)!== -1 mod p

Question 7

euler’s function:

Answer 7

ϕ(n)=no. of positive ints a <= n with gcd(a,n)=1, so ϕ(n)=|Un|

Question 8

ϕ(p^m)=:

Answer 8

(p being a prime) p^(m-1)(p-1)

Question 9

ϕ(nm), n m coprime:

Answer 9

ϕ(n)ϕ(m)

Question 10

ϕ(n) and prime factorisation:

Answer 10

n=p1^(m1)…pk^(mk), its prime factorisation, then ϕ(n)=ϕ(p1)…ϕ(pm)=p1^(m1-1)(p1-1)…pk^(mk-1)(pk-1)

Question 11

euler’s theorem:

Answer 11

a,n pos ints with gcd(a,n)=1, then a^(ϕ(n))==1 mod n

Question 12

fermat’s little theorem:

Answer 12

p prime, a not divisible by p, then a^(p-1)==1 mod p

Question 13

chinese remainder theorem:

Answer 13

n1,…,nk coprime, when given simultaneous congruences x=a1 mod n1,…,x=ak mod nk, x=n=n1…nk (multiplied) which is a single congruence class
basically multiply the ni’s to get n, for each ai find mi=n/ni, mi-ni=si, then sum aimisi and find what that is mod n

Question 14

lagrange’s polynomial congruence theorem:

Answer 14

f(x) is a polynomial with degree d and int coefficients, p is a prime, if some coefficient of f(x) is not divisible by p then f(x)=0 mod p has at most d sols modulo p

Question 15

hensel’s lemma:

Answer 15

f(x) a polynomial with int coefficients, p a prime, a an int, if there exists f(a)==0 mod p and f’(a)!==0 mod p then for all m>=1 there exists a unique int r with 1<=r<=p^m and f(r)==0 mod p^m and r==a mod p
notation is that non-singular sols modulo p lift to unique sols modulo p^m

Question 16

primitive roots:

Answer 16

[a] has order ϕ(n), so generates the entire group Un, so exists iff Un is cyclic
translated that means each [a]^i, 1<=i<=n, is a different element so all are covered
when calcing remember that if [a]^i=[1] and i!=n, it will repeat and so not cover the as yet unused elements
a^(ϕ(n)/q)!==1 mod n for each prime divisor q of n means a is a primitive root
there’s ϕ(p-1) primitive roots modulo p, p must be prime

Question 17

which Un groups are cyclic:

Answer 17

Un is cyclic iff n=1, 2, 4, p^k, or 2p^k, where p is an odd prime and k>=1

Question 18

quadratic residue:

Answer 18

[a] in Un is quadratic residue if there exists [x] in Un such that [a]=[x]^2
group of quad reses is denoted Qn

Question 19

legendre symbol:

Answer 19

(a/p)=0 if [a]=[0], 1 if [a] in Qp, and -1 if [a] in Up\Qp, p is an odd prime
(ab/p)=(a/p)(b/p)

Question 20

legendre and primitive roots:

Answer 20

(a^(i)/p)=(-1)^i

Question 21

euler’s criterion:

Answer 21

(a/p)==a^((p-1)/2) mod p
so (-1/p)=(-1)^((p-1)/2) and [-1] in Qp iff p==1 mod 4
and [2] in Qp iff p=+-1 mod 8

Question 22

quadratic reciprocity:

Answer 22

(q/p)(p/q)=(-1)^((p-1)(q-1)/4)
so if either p or q == 1 mod 4, (q/p)(p/q)=1 so (q/p)=(p/q) (cause 1 or -1 squared is 1 but 1*-1 is not)
and otherwise (q/p)=-(p/q)