1. ## modulo help

22x = 1(mod27)

how would i work this out?

2. ## Re: modulo help

You can find $x$ as follows. Suppose $x = \alpha_0 + 3\alpha_1 + 3^2\alpha_2$. Then $x \equiv \alpha_0 \pmod{3}$ and $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.

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

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

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

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

Now, you can check your answer: $22\cdot 16 = 352 = 13\cdot 27 + 1$.

3. ## Re: modulo help

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

Now, multiply the two numbers together:

$\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 $a_0 = 1$. Plugging that in, you have $1+\alpha_1 \equiv 0 \pmod{3}$, so $\alpha_1 = 2$. Now, $1+2 = 3$. Divide the result by 3 and that is the amount you are "carrying" to the left. So, you are carrying $1$ since you had one 3 from that column. So, the third column is the sum $1 + 2\alpha_0 + \alpha_1 + \alpha_2$. You want that sum (mod 3) to be zero. So, $1+2(1) + (2) + \alpha_2 = 5+\alpha_2 \equiv 0 \pmod{3}$ shows that $\alpha_2 = 1$. Plugging that in, you have $x = 1 + 3\cdot 2 + 9\cdot 1 = 16$, which is the same result as the other method.

4. ## Re: modulo help

why would you choose mod 3 and mod 9 ? where did you get these numbers from ?

5. ## Re: modulo help

It comes from looking at numbers in different bases. $27 = 3^3$, so consider numbers in base-3. If the problem had been $11x \equiv 37 \pmod{1000}$, I would have suggested looking at the equations mod 10 and mod 100.

6. ## Re: modulo help

They are factors of 27: 3(9)= 27.

7. ## Re: modulo help

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.

8. ## Re: modulo help

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

Now, multiply the two numbers together:

$\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 $a_0 = 1$. Plugging that in, you have $1+\alpha_1 \equiv 0 \pmod{3}$, so $\alpha_1 = 2$. Now, $1+2 = 3$. Divide the result by 3 and that is the amount you are "carrying" to the left. So, you are carrying $1$ since you had one 3 from that column. So, the third column is the sum $1 + 2\alpha_0 + \alpha_1 + \alpha_2$. You want that sum (mod 3) to be zero. So, $1+2(1) + (2) + \alpha_2 = 5+\alpha_2 \equiv 0 \pmod{3}$ shows that $\alpha_2 = 1$. Plugging that in, you have $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

9. ## Re: modulo help

Why factor 27? Why can't Bézout's identity be used?

10. ## Re: modulo help

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

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

Note: This assumes that $0 \le a.

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.

$\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 $i$-th column from the right, you record the sum of the digits $\pmod{p_i}$, and you "carry" the coefficient of $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 $n$ is not a power of a single prime.

11. ## Re: modulo help

Ok, here is another attempt at it:

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

Then let $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 $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 $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

$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 $i$-th column from the right (corresponding to the coefficient of $p_1\cdots p_{i-1}$) would look like this:

$\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 $c_i$ is the carry from the column to the right. Here, you want that sum to be congruent to $\beta_{i-1} \pmod{p_i}$ and the carry $c_{i+1}$ will be the greatest integer less than or equal to that sum divided by $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).

12. ## Re: modulo help

Originally Posted by SlipEternal
Given a modular equation of the form $ax \equiv b \pmod{n}$ where $a,b,n$ are all constants and $\gcd(a,n) = \gcd(b,n) = 1$, then let $n = p_1p_2\cdots p_k$ be the prime factorization of $n$.
I still claim that when $\gcd(a,n) = 1$, the simplest way to solve the equation is through Bézout's identity and the extended Euclidean algorithm.

13. ## 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.

14. ## 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).

15. ## Re: modulo help

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.

Page 1 of 2 12 Last