22x = 1(mod27)
how would i work this out?
You can find as follows. Suppose . Then and . So, you can solve the equation in steps. First, let's consider the equation mod 3, then mod 9, then mod 27.
So, shows that . Then shows that , so .
Then, finally, . So, shows that . Then, .
Now, you can check your answer: .
Here is an alternate approach: Write 22 in base-3. So, and .
Now, multiply the two numbers together:
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 . Plugging that in, you have , so . Now, . Divide the result by 3 and that is the amount you are "carrying" to the left. So, you are carrying since you had one 3 from that column. So, the third column is the sum . You want that sum (mod 3) to be zero. So, shows that . Plugging that in, you have , which is the same result as the other method.
where for all . (And similar sums for for )
Note: This assumes that .
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.
where in the -th column from the right, you record the sum of the digits , and you "carry" the coefficient of 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 is not a power of a single prime.
Ok, here is another attempt at it:
Let as in the post above (which is an ordering of the prime factors of ).
Then let .
So, the multiplication would need additional rows for the addition. The -th column from the right (corresponding to the coefficient of ) would look like this:
where is the carry from the column to the right. Here, you want that sum to be congruent to and the carry will be the greatest integer less than or equal to that sum divided by .
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).
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).