22x = 1(mod27)

how would i work this out?

Printable View

- November 14th 2013, 03:50 AMTweetymodulo help
22x = 1(mod27)

how would i work this out? - November 14th 2013, 07:40 AMSlipEternalRe: modulo help
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: . - November 14th 2013, 08:03 AMSlipEternalRe: modulo help
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. - November 14th 2013, 10:39 AMTweetyRe: modulo help
why would you choose mod 3 and mod 9 ? where did you get these numbers from ?

- November 14th 2013, 10:45 AMSlipEternalRe: modulo help
It comes from looking at numbers in different bases. , so consider numbers in base-3. If the problem had been , I would have suggested looking at the equations mod 10 and mod 100.

- November 14th 2013, 11:04 AMHallsofIvyRe: modulo help
They are factors of 27: 3(9)= 27.

- November 14th 2013, 11:10 AMSlipEternalRe: modulo help
- November 14th 2013, 11:45 AMtopsquarkRe: modulo help
- November 14th 2013, 11:52 AMemakarovRe: modulo help
Why factor 27? Why can't Bézout's identity be used?

- November 14th 2013, 12:26 PMSlipEternalRe: modulo help
Given a modular equation of the form where are all constants and , then let be the prime factorization of . Note that we are choosing an order for the prime factors of . Then, can be expressed by a sum of this form:

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. - November 14th 2013, 08:04 PMSlipEternalRe: modulo help
Ok, here is another attempt at it:

Let as in the post above (which is an ordering of the prime factors of ).

Then let .

Let .

Let .

Then

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). - November 15th 2013, 08:14 AMemakarovRe: modulo help
- November 15th 2013, 08:17 AMHartlwRe: 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. - November 15th 2013, 08:50 AMjohngRe: 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). - November 16th 2013, 02:24 PMTweetyRe: modulo help