Number Theory exam deck

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/19

encourage image

There's no tags or description

Looks like no tags are added yet.

20 Terms

1
New cards

When does b have an inverse mod n?

Exactly when gcd(b,n)=1.

2
New cards

How do you calculate a/b mod n?

a*b^(-1) mod n.

3
New cards

What does XGCD give?

x,y with gcd(a,b)=xa+yb.

4
New cards

How does XGCD give a^(-1) mod n?

If 1=xa+yn, then x mod n is a^(-1).

5
New cards

What is phi(n)?

The number of residues modulo n relatively prime to n; |Z_n*|.

6
New cards

phi(p) for prime p?

p-1.

7
New cards

phi(pq) for distinct primes p,q?

(p-1)(q-1).

8
New cards

General totient formula?

If n=product p_i^e_i, phi(n)=product p_i^(e_i-1)(p_i-1).

9
New cards

Euler's theorem?

If gcd(a,n)=1, then a^phi(n)=1 mod n.

10
New cards

How does Euler help with modular powers?

Reduce the exponent modulo phi(n), when the base is invertible.

11
New cards

Fermat's Little Theorem?

If p is prime and p does not divide a, then a^(p-1)=1 mod p.

12
New cards

Purpose of square-and-multiply?

Efficient modular exponentiation using the binary exponent.

13
New cards

CRT condition for unique reconstruction?

The moduli must be pairwise coprime.

14
New cards

CRT core idea?

Compute modulo smaller coprime factors, then reconstruct the unique result.

15
New cards

Quadratic residue q mod n?

Some x exists with x^2=q mod n.

16
New cards

If n=pq and a is a QR in Z_n*, how many roots?

Exactly four.

17
New cards

How do you find roots mod pq?

Find roots mod p and mod q, then combine sign choices with CRT.

18
New cards

Exam trigger: a/b mod n?

Find b^(-1) with XGCD, then multiply by a.

19
New cards

Exam trigger: huge exponent mod n?

Look for phi/Euler or Fermat reduction, then square-and-multiply.

20
New cards

Exam trigger: all roots mod pq?

Factor n, solve mod each prime, combine four sign pairs with CRT.