22x = 1(mod27)
how would i work this out?
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$.
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.
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.
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.
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).
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).