Divisibility and Modular Arithmetic

• a|b: a로 b를 나눌 수 있다, b=ac
• div, mod for a=dq+r,
  • quotient(몫) q = a div d
  • remainder(나머지) r = a mod d
• properties
  • a|b, a|c → a|(b+c) a|b, b|c →a|c
  • congruence 합동 : m|a-b → a≡b (mod m) a≡b, c≡d →a+c = b+d , ac≡bd if kㅗm, a/k ≡ b/k
  • (a+b) mod m = ((a mod m)+(b mod m)) mod m
  • ab mod m = ((a mod m) * (b mod m)) mod m

Integers

• Base b representation: decimal, bin, oct, hex, …
• conversion: n(10) to base b while( q) xk = q mod b q = q div b k++
• GCD(Great Common Divisor, 최대공약수)
• LCM(Least Commom Multiple, 최소공배수)
• Euclidean algorithm(유클리드 호제법)
  • gcd(a,b) = gcd(b, a mod b)
• ab = gcd(a,b)*lcm(a,b)
• Bezout’s thm: ∃s,t such that sa+tb = gcd(a,b)
• Inverse : ax ≡1 (mod m)
  • thm) for aㅗm, inverse(a) exists pf) gcd(a,m)=1 → sa+tm = 1 (bezout) → sa+tm ≡ 1 (mod m), sa ≡ 1 (mod m) ■
  • ex) find inverse of 3 mod 8
    1. 3ㅗ8: exist
    2. find s and t: 8 = 32+2 3 = 21+1 (1 나올때까지 호제법 적용) 1 = 3 - 12 1 = 3 - 1(8-32) 1 = -18 + 3*3 →s = 3, t = -1 therefore inverse of 3 is 3 ■
    • congruence equation can be solved through this. ex) 3x≡5 (mod 8) multiply inverse of 3: 9x≡15, x ≡7 ∴x = 8k+7

Number theory application hashing function, probing: 데구 참고

• PseudoRandom number for int m, 2≤a<m, 0≤c,x0<m x[n+1] = (ax[n]+c) mod m

  • ex) m=2^31-1, a = 7^5 →2^31-1 numbers generated

• check digit

  • parity check bit for n bit data data x1x2…xn, x[n+1] = (x1+x2+…+xn) mod 2
  • UPC(Universal Product Codes) for 12 digit data, sum{(1+2(i mod 2)) * xi} ≡ 0 (mod 10)

  ex) last digit of 79357343104_ ? sol) sum() = 98+x12 ≡ 0 (mod 10), x12 = 2

  • ISBN: 9 digit+check digit x10 = sum(i*xi) (mod 11)

  ex) 007288008_? 10+20+37+… +98= 189 ≡ 2 (mod 11) ∴x10 = 2