Pages

Modulo for rational numbers II


In the previous post, we have learned about modulo for rational numbers. Today, we will continue on this topic and will learn about some properties of this modulo.

First of all, let us look at some examples and review the definition: $$\frac{14}{5} =_{Q} ~0 \pmod{7}, $$ $$ \frac{16}{55} =_{Q} ~\frac{9}{55} =_{Q} ~\frac{2}{55} \pmod{7},$$ $$\frac{1}{4} =_{Q} ~\frac{8}{4} =_{Q} ~2 \pmod{7}, \dots$$


Definition. Let $n$ be an integer, and $\alpha$, $\beta$ two rational numbers. We say that $\alpha$ is equal to $\beta$ modulo $n$, and write $$\alpha =_{Q} ~\beta \pmod{n}$$ if and only if there exists an integer $k$ co-prime to $n$ such that $k(\alpha - \beta)$ is an integer and $$k(\alpha - \beta) = 0 \pmod{n}.$$




To distinguish between the modulo of rationals and the modulo of integers , we use the notation "$=_{Q}$" as above to denote the modulo of rationals, the usual notation "$=$" indicates our normal modulo of integers.

Now, an integer is obviously a rational, so if $a$ and $b$ are two integers then what is the difference between, when we say $a$ is equal to $b$ modulo $n$ as rationals, and $a$ is equal to $b$ modulo $n$ as integers? The answer is, there is no difference. These two conditions are actually equivalent as the following theorem asserts.

Theorem. Assume that $n$, $a$, $b$ are integers. Then $$a = _{Q} ~b \pmod{n}$$ is equivalent to the condition $$a = b \pmod{n}.$$

For example, we have $$9 = 2 \pmod{7}$$ and also $$9 =_{Q} 2 \pmod{7}.$$






Let us now look at some properties of this modulo.

Addition Rule:
If $$\alpha =_{Q} ~\beta \pmod{n}$$ and $$\chi =_{Q} ~\psi \pmod{n}$$ then $$\alpha + \chi =_{Q} ~\beta + \psi \pmod{n}.$$

Addition Rule (special case):
If $$\alpha =_{Q} ~\beta \pmod{n}$$ then $$\alpha + \chi =_{Q} ~\beta + \chi \pmod{n}.$$

Subtraction Rule:
If $$\alpha =_{Q} ~\beta \pmod{n}$$ and $$\chi =_{Q} ~\psi \pmod{n}$$ then $$\alpha - \chi =_{Q} ~\beta - \psi \pmod{n}.$$

Subtraction Rule (special case):
If $$\alpha =_{Q} ~\beta \pmod{n}$$ then $$\alpha - \chi =_{Q} ~\beta - \chi \pmod{n}.$$

Multiplication Rule:
If we have a rational number of the form $$\chi = \frac{x}{y},$$ where $y$ is co-prime to $n$, and if $$\alpha =_{Q} ~\beta \pmod{n}$$ then $$\chi ~\alpha  =_{Q} ~\chi ~\beta \pmod{n}.$$

Multiplication Rule (special case):
If $$\alpha =_{Q} ~\beta \pmod{n},$$ then for any integer $x$, we have $$x ~\alpha  =_{Q} ~x ~\beta \pmod{n}.$$

Multiplication Rule (special case):
If $$\alpha =_{Q} ~\beta \pmod{n}$$ then for any integer $y$ co-prime to $n$, we have $$\frac{1}{y} ~\alpha  =_{Q} ~\frac{1}{y} ~\beta \pmod{n}.$$





    Now, after learning about modulo for rationals, we can review the proof of Wilson's theorem here. We will see that this proof can be explained beautifully in the language of modulo for rationals.

    In the next post, we will present two proofs of Wilson's theorem by using modulo of rationals. One proof will use Newton's interpolation formula, and the other will use Lagrange's formula.

    Hope to see you again there.




    Homework.

    1. Suppose that $n$ is an integer and $\alpha$, $\beta$, $\gamma$ are rationals. Prove that if $$\alpha =_{Q} ~\beta \pmod{n}$$ and $$\beta =_{Q} ~\gamma \pmod{n}$$ then $$\alpha =_{Q} ~\gamma \pmod{n}.$$

    2. Prove the following Inverse Rule
    Suppose that $n$, $a$, $b$ are integers. If $$\gcd(a,n)= \gcd(b,n)=1$$ and $$a=b \pmod{n}$$ then $$\frac{1}{a}=_{Q} ~\frac{1}{b} \pmod{n}.$$

    3. Prove the following Multiplication Rule
    Suppose that $$\alpha = \frac{a}{b}, ~\beta = \frac{c}{d}, ~\chi = \frac{x}{y}, ~\psi = \frac{s}{t},$$ where all the denominators $b, d, y, t$ are all co-prime to $n$.
    If $$\alpha =_{Q} ~\beta \pmod{n}$$ and $$\chi =_{Q} ~\psi \pmod{n}$$ then $$\alpha ~ \chi =_{Q} ~\beta ~ \psi \pmod{n}.$$

    4. Prove the following Exponentiation Rule
    Suppose that $$\alpha = \frac{a}{b}, ~\beta = \frac{c}{d},$$ where the denominators $b, d$ are co-prime to $n$.
    If $$\alpha =_{Q} ~\beta \pmod{n}$$ then $$\alpha^k =_{Q} ~\beta^k \pmod{n}.$$



    No comments:

    Post a Comment