Month: May 2018

Pulverizer is a method similar to Euclead’s algorithm that finds the greatest common divisor (GCD) of two integers. It logs the calculations so that how such GCD can be achieved with linear combination of the two integers is also found.

Here is a simple example in C:

int pulverizer(long a, long b){
    long xa[] = {1,0};
    long xb[] = {0,1};
    
    while(a != b){
        if(a > b){
            a = a - b;
            xa[0] = xa[0] - xb[0];
            xa[1] = xa[1] - xb[1];
        }else{
            b = b - a;
            xb[0] = xb[0] - xa[0];
            xb[1] = xb[1] - xa[1];
        }
    }
    
    printf("GCD(a,b) = %ld; coefficients can be (%ld, %ld) or (%ld, %ld).\n", a, xa[0], xa[1], xb[0], xb[1]);
}

Pulverizer is very useful in finding the multiplicative inverse of an integer $$k$$ modulo a relatively prime number $$p$$. Consider the following:$$!\gcd(k,p) = 1$$ There exists a pair of integers $$(s,t)$$ such that $$!sp + tk = 1$$

Therefore, $$1-tk = sp \implies p | 1-tk \implies tk \equiv 1 \pmod{p}$$.

Alternatively, Fermat’s little theorem and its generalization, Euler’s theorem, can also be used to find the multiplicative inverse.

Euler’s Theorem

If $$a$$ and $$n$$ are relatively prime, then $$!a^{\phi(n)} \equiv 1 \pmod{n}$$ where $$\phi(n)$$ is the number of integers in $$[1,n]$$ that are relatively prime to $$n$$.

The Euler’s Totient Function

Single Prime

First, we examine function $$\phi(p^k)$$, where $$p$$ is a prime:

In $$\{1,2,3,…,p^k\}$$,  the only integers that are not relatively prime to $$p^k$$ are the multiples of $$p$$, and there are $$\frac{p^k}{p} $$ of them. Therefore $$!\begin{align}\phi(p^k) &= p^k – \frac{p^k}{p} \\ &= p^k (1- \frac{1}{p})\end{align}$$

Multiplicative Function

Lemma: if $$a$$ and $$b$$ are relatively prime, then $$\phi(ab) = \phi(a)\phi(b)$$

Proof:

We first arrange the numbers $$\{1,2,3,…,ab\}$$ by rows to a $$b \times a$$ matrix:

$$!\begin{bmatrix} 1 & 2 &  \dots & a \\
a+1 & a+ 2&  \dots & 2a\\
2a+ 1 & 2a+ 2 &  \dots & 3a\\
\vdots & \vdots & \ddots & \vdots\\
(b-1)a + 1 & (b-1)a +2 &\dots &  ab
\end{bmatrix}$$

This way, numbers in the same column are congruent to each other modulo $$a$$. Specifically, the element $$u_{ij}$$ at row i has the following property:

$$!\mathrm{rem}(u_{ij}, a) = j$$

We know (same as Euclid’s algorithm) that, $$!\gcd(u_{ij},a) = \gcd(\mathrm{rem}(u_{ij}, a), a) = \gcd(j,a)$$

This is to say that, if $$j \in \{1,2,3,…,a\}$$ satisfies $$\gcd(j,a) = 1$$, all the numbers in column $$j$$ are relatively prime to $$a$$, and there are $$\phi(a)$$ such columns in total.

Now let’s examine a column. The numbers in column $$j$$ can be written as: $$!\begin{bmatrix}
j\\
j+a\\
j+2a\\
\vdots\\
j+(b-1)a
\end{bmatrix}$$

Corollary: the remainders of the numbers in a column modulo b form a permutation of the sequence $$\{0,1,2,3,…,b-1\}$$.

This is equivalent to that each of the $$b$$ numbers in the row has a different remainder modulo b.We can prove it by contradiction:

Suppose $$!j+sa \equiv j+ta \pmod{b}$$ where $$b-1 \geq s > t \geq 0$$, we have $$!sa \equiv ta \pmod{b}$$ $$!(s-t)a \equiv 0 \pmod{b}$$

We know that $$\gcd(a,b) = 1$$, and (s-t) must be smaller than $$b$$, so there is contradiction.

Now, this corollary shows that every column has $$\phi(b)$$ numbers that are relatively prime to $$b$$.

Number $$u_ij$$ is relatively prime to $$ab$$ if and only if it is relatively to both $$a$$ and $$b$$. In other words, it must be on one of the $$\phi(a)$$ columns described above, and in one of the $$\phi(b)$$ positions on that column. Therefore, $$!\phi(ab) = \phi(a)\phi(b)$$

This can be applied to any positive integer $$n = p_1^{k_1}p_2^{k_2}p_3^{k_3}…p_r^{k_r} $$, where $$p$$ and $$k$$ are from the factored form under the fundamental theorem of arithmetic. We have $$!\phi(n) = n\prod_{p|n}(1 – \frac{1}{p})$$

Proof of the Theorem

We’ve finally come to prove that $$a^{\phi(n)} \equiv 1 \pmod{n}$$.

Lemma: Let $$m_1,m_2,m_3,…,m_{\phi(n)} $$ be the $$\phi(n)$$ integers that are relatively prime to n and in the range of $$[1, n]$$. Then there will no two of them, such that $$am_j \equiv am_i \pmod{n}$$, and all the remainders $$\mathrm{rem}(am_1, n), \mathrm{rem}(am_2, n), \mathrm{rem}(am_3, n), …, \mathrm{rem}(am_\phi(n), n)$$ form a permutation of the sequence $$\{m_1,m_2,m_3,…,m_{\phi(n)} \}$$.

Proof by contradiction:

Assume there is a pair of $$i$$ and $$j$$, such that $$am_j \equiv am_i \pmod{n}$$. Then $$a (m_j – m_i) \equiv 0 \pmod{n}$$. Since $$\gcd(a,n) = 0$$, $$m_j – m_i $$ must be divisible by $$n$$, which leads to contradiction. So we proved the difference between any $$am_i$$ and $$am_j$$. Also, $$\gcd(\mathrm{rem}(am, n), n) = gcd(am, n) = 1$$. Therefore, by definition, $$\mathrm{rem}(am, n) \in \{m_1,m_2,m_3,…,m_{\phi(n)} \}$$.

With this lemma, we can compute the congruence of the product of $$m_1,m_2,m_3,…,m_{\phi(n)}$$:

$$!\begin{align}
\prod_{i=1}^{\phi(n)}am_i & = a^{\phi(n)}\prod_{i=1}^{\phi(n)}\\
a^{\phi(n)}\prod_{i=1}^{\phi(n)}m_i & \equiv \prod_{i=1}^{\phi(n)}m_i \pmod{n}
\end{align}$$

For simplicity, we assign $$M = \prod_{i=1}^{\phi(n)}m_i$$, so we have $$!(a^{\phi(n)} – 1) M \equiv 0 \pmod{n}$$

Because $$M$$ is relatively prime to $$n$$, $$a^{\phi(n)} – 1$$ must be divisible by $$n$$.

Done.