3 minute read

> Go to Number Theory Contents

맛보기

Example

은행 업무 중 흔하게 일어나는 실수로는 interchange two of the digits(두개의 숫자를 바꿔서 입력, 5924 -> 5294)가 있다.
올바른 금액과 2개의 digit를 바꾼 금액이 항상 9로 나누어 떨어진 다는 것을 증명해라!
\begin{align}
n &\equiv \sum a_j \pmod{9} \nonumber \newline m &\equiv \sum b_j \pmod{9} \nonumber \newline n-m &\equiv \sum a_j - \sum b_j \pmod{9} \nonumber \newline &\equiv 0 \nonumber \newline \end{align}

마술?
다음의 과정을 밟아보자!

  1. n개의 digits가 있는 양의 정수를 하나 골라라! 372953
  2. 다음으로, 1번에서 고른 숫자의 digits를 가지고 순서를 바꿔 다른 정수를 만들어라! 923357
  3. 큰 수에서 작은 수를 빼라! 923357 - 372953 = 550404
  4. 0이 아닌 한가지 digit를 골라라! 550404
  5. 고른 digit를 제외한 나머지 digits들을 말해라! 0, 0, 4, 4, 5
  6. 이렇게 되면, 남은 1개의 숫자가 뭔지 맞출 수 있게 된다!
    $(0+0+4+4+5) \equiv x \pmod{9}$, $x = 5$

Binary

Binary? 0과 1로 이루어진 숫자, 2진법
Find the least residue of $848^{187} \pmod{1189}$ -> 숫자가 너무 크다…
Note: $848^{2n+1} = (848^{2n})^2$
Hence, 187을 base 2 representation으로 나타내보자 (binary representation)

$187 = a_k(2^k) + a_{k+1}(2^{k+1}) + \cdots + a_1(2^1) + a_0$ where $0 \leq a_j < 2$ (least residue mod 2)
$187 = 2(93)+1$. Hence, $a_0ss = 1$ and $93 = a_k(2^{k-1}) + a_{k-1}(2^{k-2}) + \cdots + a_2(2^1) + a_1$
Now, $93 = 2(46)+1$. Hence, $a_1 = 1$ and $46 = a_k(2^{k-2}) + \cdots + a_3(2^1) + a_2$, etc.
We can find that $187 = (10111011)_2 = 2^7+2^5+2^4+2^3+2^1+2^0$

Then $848^{187} = 848^{2^7+2^5+2^4+2^3+2^1+2^0} = 848^{2^7}+848^{2^5}+848^{2^4}+848^{2^3}+848^{2^1}+848^{2^0}$
$848^{2^1} \equiv (848^{2^0})^2 \equiv 719104 \equiv 948 \pmod{1189}$ <- least residue
$848^{2^2} \equiv (848^{2^1})^2 \equiv 948^2 \equiv 898704 \equiv * \pmod{1189}$
$848^{2^3} \equiv (\ast)^2 \equiv \text{**} \pmod{1189}$, etc.
Then, $848^{187} \equiv (1035)(980)(223)(297)(948)(848)$
$\equiv (83)(836)(140) \equiv 190 \pmod{1189}$

848의 지수를 여러 작은 숫자들로 쪼개서, 작은 숫자들 끼리 mod를 계산할 수 있다!

Congurence

Congurence class

What does it mean to solve a Congruence?
Congurence를 푼다는 건 무슨 의미?
To solve the equation $x^2+x-2=0$, we must find all values of $x$ making the equation true.
Consider $x^2+x-2 \equiv 0 \pmod{7}$. () integral solution을 찾는것.
Suppose $x$ satisfies ()
만약 $x_1 \equiv x \pmod{7}$라면,
$x_1^2 \equiv x^2 \pmod{7}$또한 만족한다.
결국, $x_1$ is also a solution이 된다.
따라서 (*) has infinitly many solutions.

$m > 0$이 정수라고 가정할 때, congurence class mod m 이라고 하면 set of all integers congurent mod to some fixed integer $x$이다.

Complete residue system

complete residue system mod m 라는 말은 각각의 congurence class mod m에서 정확히 하나의 정수씩만 담겨있는 set을 의미한다.

Example
${ -6, -2, 2 } $ is complete residue system$\mod{3}$
$-6 = 3a + 0$
$-2 = 3a + 1$
$2 = 3a + 2$

Least complete solution

F를 polynomial with integral coefficients라고 하고 $F(x) \equiv 0 \pmod{m}$이라고 하자. (**)
${x_1, x_2, … x_k}$를 complete solution to the congurence (**) 라고 하면, the set of all solutions in some complete residue system mod $m$이다.
이것은 _least complete solution_라고 하며, set of all solutions among $0, 1, \cdots m-1$이다.

Example

(*)에 대하여, complete solution은 {1, 5}이고;
least complete solution은 {1, 5}이다.

{a, a+1, a+2, $\cdots$, a+(m-1)} $\mod{m}$
is a complete residue system, mod $m$
\begin{align} &a+i &&\equiv a+j \mod{m} \nonumber \newline \Rightarrow &i &&\equiv j \mod{m} \quad(0 \leq i, j \leq m-1) \nonumber \newline
\Rightarrow &m|(i-j) &&\Rightarrow i = j \quad |i-j| < m\nonumber\newline \therefore a+j \not\equiv a+j \pmod{m} \quad \text{if } i \neq j \nonumber \end{align}

Linear Congurence

Linear Congurece: $ax \equiv c \pmod{m}$ (***) \begin{align} ax &\equiv c \pmod{m} \nonumber\newline ax-c &\equiv 0 \pmod{m} \nonumber\newline m &| ax-c \nonumber\newline ax-c &= my \quad (y \in \mathbb{Z}) \nonumber\newline ax-my &= c \nonumber \end{align}

Solving (***) is equivalent to solving $ax-my=c$
Hence (***) has a solution if and only if $\gcd({a}, {m}) | c$

Practice problems #11

  1. Use the binary exponentiation algorithm (what we did in class is called such) to compute 1953 (mod 503).

  2. True or False. Justify.

    • 2-1. If gcd(a, m) = 1, then
      \begin{align} {c, c+a, c+2a, c…, c+(m-1)a} \nonumber \end{align} is a complete residue system mod m for any integer c.

    • 2-2. There is a complete solution containing 4 elements to the congruence equation \begin{align} 10x^3+20x^2+10 \equiv 0 \pmod{127} \nonumber \end{align}

You May Also Enjoy