Solving systems of equations with Modular Arithmetic can be complex, especially with the following equations: ( a 0 x + a 0 2 ) e ≡ C 0 ( m o d n ) ( a 1 x + a 1 2 ) e ≡ C 1 ( m o d n )

Question

Solving systems of equations with Modular Arithmetic can be complex, especially with the following equations:  (      a    0    x  +                    a        0              2        )    e    ≡      C    0      (  m  o  d    n  )  (      a    1    x  +                    a        1              2        )    e    ≡      C    1      (  m  o  d    n  )

lavarcar2d2 · Accepted Answer

Powers often simplify modulos. For example, it is well known that all cubes are either   0,   1, or   −  1 (mod   7  )). You can verify this yourself by simply cubing all numbers modulo   7 (that is, cube   0  ,  1  ,  2  ,  3  ,  4  ,  5  ,, and   6 and you will find all results are   0,   1, or   −  1 (mod   7  )) ). Here you have two numbers raised to a power   e. Without too much difficulty you should be able to find the set of all modulo values (mod   n  )) that result from raising a number to the eth power.       C    0   and       C    1   will be two of those. Match them to the corresponding modulo you raised to the   eth power to get the set of possible values for       a    0    x  +      a    0    2   and       a    1    x  +      a    1    2   (mod   n  )). From there it is merely a matter of using some simple algebra to arrive at your solution.

Solving systems of equations with Modular Arithmetic can be complex, especially with the following equations: (a_0x+a_0^2)^e≡C_0(modn), (a_1x+a_1^2)^e≡C1(modn)

Answered question

Answer & Explanation

New Questions in Algebra I