# modulo help

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Nov 14th 2013, 02:50 AM
Tweety
modulo help
22x = 1(mod27)

how would i work this out?
• Nov 14th 2013, 06:40 AM
SlipEternal
Re: modulo help
You can find $\displaystyle x$ as follows. Suppose $\displaystyle x = \alpha_0 + 3\alpha_1 + 3^2\alpha_2$. Then $\displaystyle x \equiv \alpha_0 \pmod{3}$ and $\displaystyle x \equiv \alpha_0 + 3\alpha_1 \pmod{9}$. So, you can solve the equation in steps. First, let's consider the equation mod 3, then mod 9, then mod 27.

$\displaystyle 22x \equiv x \pmod{3}$

$\displaystyle 22x \equiv 4x \pmod{9}$

So, $\displaystyle x \equiv 1 \pmod{3}$ shows that $\displaystyle \alpha_0 = 1$. Then $\displaystyle 4(1+3\alpha_1) \equiv 1 \pmod{9}$ shows that $\displaystyle 3\alpha_1 \equiv 6 \pmod{9}$, so $\displaystyle \alpha_1 = 2$.

Then, finally, $\displaystyle 22x = 22(1 + 3\cdot 2 + 9\alpha_2) = 22\cdot 7 + 198 \alpha_2 \equiv 19 + 9\alpha_2 \pmod{27}$. So, $\displaystyle 9\alpha_2 \equiv 9 \pmod{27}$ shows that $\displaystyle \alpha_2 = 1$. Then, $\displaystyle x = 1 + 3\cdot 2 + 9\cdot 1 = 16$.

Now, you can check your answer: $\displaystyle 22\cdot 16 = 352 = 13\cdot 27 + 1$.
• Nov 14th 2013, 07:03 AM
SlipEternal
Re: modulo help
Here is an alternate approach: Write 22 in base-3. So, $\displaystyle 22 = 211_3 = 1 + 3\cdot 1 + 9\cdot 2$ and $\displaystyle x = (\alpha_2\alpha_1\alpha_0)_3 = \alpha_0 + 3\alpha_1 + 9\alpha_2$.

Now, multiply the two numbers together:

$\displaystyle \begin{array}{cccccc} & & & 2 & 1 & 1 \\ \times & & & \alpha_2 & \alpha_1 & \alpha_0 \\ \hline & & & 2\alpha_0 & \alpha_0 & \alpha_0 \\ & & 2\alpha_1 & \alpha_1 & \alpha_1 & 0 \\ + & 2\alpha_2 & \alpha_2 & \alpha_2 & 0 & 0 \\ \hline & ? & ? & 0 & 0 & 1\end{array}$

This addition should feel familiar from multiplying two numbers base-10. Only now, for each column, you record the result (mod 3) and carry each multiple of 3. So, the right-most column shows that $\displaystyle a_0 = 1$. Plugging that in, you have $\displaystyle 1+\alpha_1 \equiv 0 \pmod{3}$, so $\displaystyle \alpha_1 = 2$. Now, $\displaystyle 1+2 = 3$. Divide the result by 3 and that is the amount you are "carrying" to the left. So, you are carrying $\displaystyle 1$ since you had one 3 from that column. So, the third column is the sum $\displaystyle 1 + 2\alpha_0 + \alpha_1 + \alpha_2$. You want that sum (mod 3) to be zero. So, $\displaystyle 1+2(1) + (2) + \alpha_2 = 5+\alpha_2 \equiv 0 \pmod{3}$ shows that $\displaystyle \alpha_2 = 1$. Plugging that in, you have $\displaystyle x = 1 + 3\cdot 2 + 9\cdot 1 = 16$, which is the same result as the other method.
• Nov 14th 2013, 09:39 AM
Tweety
Re: modulo help
why would you choose mod 3 and mod 9 ? where did you get these numbers from ?
• Nov 14th 2013, 09:45 AM
SlipEternal
Re: modulo help
It comes from looking at numbers in different bases. $\displaystyle 27 = 3^3$, so consider numbers in base-3. If the problem had been $\displaystyle 11x \equiv 37 \pmod{1000}$, I would have suggested looking at the equations mod 10 and mod 100.
• Nov 14th 2013, 10:04 AM
HallsofIvy
Re: modulo help
They are factors of 27: 3(9)= 27.
• Nov 14th 2013, 10:10 AM
SlipEternal
Re: modulo help
Quote:

Originally Posted by HallsofIvy
They are factors of 27: 3(9)= 27.

If you are learning the Chinese Remainder Theorem, then HallsofIvy brings up a good point, and this is the way you want to think about it.
• Nov 14th 2013, 10:45 AM
topsquark
Re: modulo help
Quote:

Originally Posted by SlipEternal
Here is an alternate approach: Write 22 in base-3. So, $\displaystyle 22 = 211_3 = 1 + 3\cdot 1 + 9\cdot 2$ and $\displaystyle x = (\alpha_2\alpha_1\alpha_0)_3 = \alpha_0 + 3\alpha_1 + 9\alpha_2$.

Now, multiply the two numbers together:

$\displaystyle \begin{array}{cccccc} & & & 2 & 1 & 1 \\ \times & & & \alpha_2 & \alpha_1 & \alpha_0 \\ \hline & & & 2\alpha_0 & \alpha_0 & \alpha_0 \\ & & 2\alpha_1 & \alpha_1 & \alpha_1 & 0 \\ + & 2\alpha_2 & \alpha_2 & \alpha_2 & 0 & 0 \\ \hline & ? & ? & 0 & 0 & 1\end{array}$

This addition should feel familiar from multiplying two numbers base-10. Only now, for each column, you record the result (mod 3) and carry each multiple of 3. So, the right-most column shows that $\displaystyle a_0 = 1$. Plugging that in, you have $\displaystyle 1+\alpha_1 \equiv 0 \pmod{3}$, so $\displaystyle \alpha_1 = 2$. Now, $\displaystyle 1+2 = 3$. Divide the result by 3 and that is the amount you are "carrying" to the left. So, you are carrying $\displaystyle 1$ since you had one 3 from that column. So, the third column is the sum $\displaystyle 1 + 2\alpha_0 + \alpha_1 + \alpha_2$. You want that sum (mod 3) to be zero. So, $\displaystyle 1+2(1) + (2) + \alpha_2 = 5+\alpha_2 \equiv 0 \pmod{3}$ shows that $\displaystyle \alpha_2 = 1$. Plugging that in, you have $\displaystyle x = 1 + 3\cdot 2 + 9\cdot 1 = 16$, which is the same result as the other method.

Does this always work? It doesn't bear any resemblance to the method for the Chinese Remainder theorem that I looked up about a year ago.

-Dan
• Nov 14th 2013, 10:52 AM
emakarov
Re: modulo help
Why factor 27? Why can't Bézout's identity be used?
• Nov 14th 2013, 11:26 AM
SlipEternal
Re: modulo help
Quote:

Originally Posted by topsquark
Does this always work? It doesn't bear any resemblance to the method for the Chinese Remainder theorem that I looked up about a year ago.

-Dan

Given a modular equation of the form $\displaystyle ax \equiv b \pmod{n}$ where $\displaystyle a,b,n$ are all constants and $\displaystyle \gcd(a,n) = \gcd(b,n) = 1$, then let $\displaystyle n = p_1p_2\cdots p_k$ be the prime factorization of $\displaystyle n$. Note that we are choosing an order for the prime factors of $\displaystyle n$. Then, $\displaystyle a,b,x$ can be expressed by a sum of this form:

$\displaystyle a = \alpha_0 + \alpha_1p_1 + \alpha_2p_1p_2 + \cdots + \alpha_{k-1}\left(\prod_{i = 1}^{k-1}p_i\right)$ where $\displaystyle \alpha_i \in \mathbb{Z}, 0\le \alpha_i < p_{i+1}$ for all $\displaystyle i = 0,1,\ldots, k-1$. (And similar sums for for $\displaystyle b,x$)

Note: This assumes that $\displaystyle 0 \le a<n, 0 \le b<n,\text{ and }0 \le x<n$.

This is similar to writing a number in a different base, only each digit is changing bases. Then you can figure out the multiplication

Edit: This is currently not correct... I will revisit it later.

$\displaystyle \begin{array}{cccccccc} & & & & \alpha_{k-1} & \cdots & \alpha_1 & \alpha_0 \\ \times & & & & \chi_{k-1} & \cdots & \chi_1 & \chi_0 \\ \hline & & & & \chi_0 \alpha_{k-1} & \cdots & \chi_0 \alpha_1 & \chi_0 \alpha_0 \\ & & & \chi_1 \alpha_{k-1} & \chi_1 \alpha_{k-2} & \cdots & \chi_1 \alpha_0 & 0 \\ & & & \vdots & \cdots & \vdots & \cdots & 0 \\ + & \chi_{k-1}\alpha_{k-1} & \cdots & \chi_{k-1}\alpha_1 & \chi_{k-1}\alpha_0 & 0 & \cdots & 0 \\ \hline & ? & \cdots & ? & \beta_{k-1} & \cdots & \beta_1 & \beta_0\end{array}$

where in the $\displaystyle i$-th column from the right, you record the sum of the digits $\displaystyle \pmod{p_i}$, and you "carry" the coefficient of $\displaystyle p_i$ from that sum.

--I will revisit this later. I am not doing this quite right. There is a way to make this process precise, but I am not there yet. Currently, this process can fail if $\displaystyle n$ is not a power of a single prime.
• Nov 14th 2013, 07:04 PM
SlipEternal
Re: modulo help
Ok, here is another attempt at it:

Let $\displaystyle n = \prod_{i=1}^m p_i$ as in the post above (which is an ordering of the prime factors of $\displaystyle n$).

Then let $\displaystyle a = \sum_{i = 0}^{m-1} \alpha_i \left(\prod_{j = 1}^i p_j \right), \forall 0 \le i < m, 0 \le \alpha_i < p_{i+1}$.

Let $\displaystyle x = \sum_{i = 0}^{m-1} \chi_i \left(\prod_{j = 1}^i p_j \right), \forall 0 \le i < m, 0 \le \chi_i < p_{i+1}$.

Let $\displaystyle b = \sum_{i = 0}^{m-1} \beta_i \left(\prod_{j = 1}^i p_j \right), \forall 0 \le i < m, 0 \le \beta_i < p_{i+1}$.

Then

$\displaystyle ax = \sum_{i=0}^{m-1} \left[ \left(\sum_{j=0}^{i}\alpha_i\chi_j \left(\prod_{k=1}^j p_k \right) \right) + \left(\sum_{j=0}^{i-1}\alpha_j\chi_i \left(\prod_{k=1}^j p_k\right) \right) \right] \left(\prod_{k=1}^i p_k \right)$

So, the multiplication would need additional rows for the addition. The $\displaystyle i$-th column from the right (corresponding to the coefficient of $\displaystyle p_1\cdots p_{i-1}$) would look like this:

$\displaystyle \begin{array}{cc} & c_i \\ & \alpha_{i-1}\chi_0 \\ & \alpha_{i-1}\chi_1p_1 \\ & \alpha_{i-1}\chi_2p_1p_2 \\ & \vdots \\ & \alpha_{i-1}\chi_{i-1}p_1p_2\cdots p_{i-1} \\ & \chi_{i-1}\alpha_0 \\ & \chi_{i-1}\alpha_1p_1 \\ & \vdots \\ + & \chi_{i-1}\alpha_{i-2}p_1\cdots p_{i-2} \\ \hline & \beta_{i-1}\end{array}$

where $\displaystyle c_i$ is the carry from the column to the right. Here, you want that sum to be congruent to $\displaystyle \beta_{i-1} \pmod{p_i}$ and the carry $\displaystyle c_{i+1}$ will be the greatest integer less than or equal to that sum divided by $\displaystyle p_i$.

While it may not look like it, this method is actually very similar to the Chinese Remainder Theorem (you can use the theorem to prove this process works).
• Nov 15th 2013, 07:14 AM
emakarov
Re: modulo help
Quote:

Originally Posted by SlipEternal
Given a modular equation of the form $\displaystyle ax \equiv b \pmod{n}$ where $\displaystyle a,b,n$ are all constants and $\displaystyle \gcd(a,n) = \gcd(b,n) = 1$, then let $\displaystyle n = p_1p_2\cdots p_k$ be the prime factorization of $\displaystyle n$.

I still claim that when $\displaystyle \gcd(a,n) = 1$, the simplest way to solve the equation is through Bézout's identity and the extended Euclidean algorithm.
• Nov 15th 2013, 07:17 AM
Hartlw
Re: modulo help
22x=1(mod27)

From Euclidean algorithm:
27=1*22+5
22=4*5+2
5= 2*2+1

Substituting successiveley gives:
1=9*27-11*22
1-(-11)22=9*27
x=-11

It’s a little short on detail, but it illustrates a standard method.
• Nov 15th 2013, 07:50 AM
johng
Re: modulo help
Hi,
Here's yet another approach:
Since 22 is prime to 27, 22 has a multiplicative inverse mod 27, say x. With more arithmetic than I like to do you get x = 16. So just multiply both sides of your congruence by 16 and you're done.

Alternatively, since -5 is the same as 22 mod 27, the original congruence becomes -5x = 1 (mod 27) or 5x = -1 (mod 27). Now I'm willing to do arithmetic to find the inverse of 5 mod 27. Of course, I need check only x's prime to 27. So the relevant multiples of 5 are 5, 10, 20, 25, 35, 40, 50, 55; whoa, stop. 55=5*11 is 1 mod 27. So x = -11 (mod 27) = 16 (mod 27).
• Nov 16th 2013, 01:24 PM
Tweety
Re: modulo help
Quote:

Originally Posted by Hartlw
22x=1(mod27)

From Euclidean algorithm:
27=1*22+5
22=4*5+2
5= 2*2+1

Substituting successiveley gives:
1=9*27-11*22
1-(-11)22=9*27
x=-11

It’s a little short on detail, but it illustrates a standard method.

Hello,

Thank you, I understand this method, and got up to

1 = 9*27 -11*22,

but I do not understand how you know that x = - 11? Can you please explain?

Thank you.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last