Question 1

What's the better way?
Is it 7^4^4^2?
Also, here's a puzzle:
prove 999,999 is a multiple of 7 using modular arithmetic.

Answer is in comments.

Accepted Answer

1) square root of 256 == 16.     square root of 16 == 4.

7^4 modulo 13 == 9.     7^256 modulo 13 == 9.

7^4^4^2 is not the better way because the number is larger than 7^10 and the given calculator's memory cannot hold numbers larger than that.

2) 999999 modulo 7 == 0, use prime factorization to tease out the 7 and prove it's a multiple of 7.

Question 2

Is there a proof for the modular exponentiation property
 (A^B) mod C = ((A mod C) ^ B) mod C ?

Accepted Answer

It is just repeated application of the property for multiplication
i.e. (X * Y) mod Z = (X mod Z * Y mod Z) mod Z

A^B mod C = ( A^(B-1) * A ) mod C 
A^B mod C = ( A^(B-1) mod C * A mod C) mod C
A^B mod C = ( (A^(B-2) * A) mod C * A mod C) mod C
A^B mod C = ( (A^(B-2) mod C * A mod C) mod C * A mod C) mod C
A^B mod C = ( A^(B-2) mod C * A mod C * A mod C) mod C
...
A^B mod C = ( A mod C * A mod C * .... A mod C) mod C
(with B  'A mod C' terms on the right)
 A^B mod C = ((A mod C)^B) mod C

Hope this makes sense

Question 3

What if the exponent B is negative? For instance, I read that 42^(-1) mod5 = 3=y. How do we arrive at that? According to what's written above, 
y= (42 mod 5)^-1 mod 5 = 2^-1 mod 5 = 1/2 mod5 
Now I'm getting stuck. Could someone help me?

Accepted Answer

In modular arithmetic A^-1 (mod B) denotes the modular inverse of A (mod B).
Check out:
https://www.khanacademy.org/math/applied-math/cryptography/modarithmetic/a/modular-inverses

The following property holds in the regular math that you are used to and also holds in modular math:
A^B * A^-C = A^(B-C)
Example 1: A^-1 * A^1  = A^0 = 1	e.g. 2^-1 * 2 = 1 
Example 2: A^2  * A^-1 = A^1 = A	e.g. 2^2 * 2^-1 = 2

So here's how we could solve 42^(-1) mod5 :
42 mod 5 ≡ 2
We can see that  2 * 3 = 6 and 6 ≡ 1 (mod 5), thus 2^-1=3 (mod 5)  
(note that 2 * 2^-1 = 1),

(Just to show that it works on 42 we can write:
42 * 3 = 126
126 mod 5 = 1
Thus 42^-1 mod 5 = 3
)

Hope this makes sense

Question 4

if i have 
x+y ≡  6 (mod 7)
3x - y ≡ 2 (mod 7)
x-y ≡  ? (mod 7)

Accepted Answer

```
 x  +  y ≡  6 (mod 7)
3x  -  y ≡  2 (mod 7)
```
is a system of linear congruences
You would solve it in the same manner that you would solve a system of linear equations with the following exception:
- you can't divide, so every time you would divide when solving a system of linear equations, you instead multiply by the modular inverse when solving a system of linear congruences

This would give you the values of x and y which you could simply plug into the last congruence for the solution.

e.g.
```
2x  +  5y ≡ 6 (mod 13)
3x  -  7y ≡ 2 (mod 13)
```
Step 1) check the determinant

det = ((2 * -7) - (3 * 5)) mod 13 = -29 mod 13
-29 mod 13 = 10
The determinant is non-zero so we can find a unique solution (mod 13)
If it was 0 there would either be no solutions, or infinite solutions (mod 13)

Step 2) solve the linear congruence

We want the coefficient of the x to be 1 in the first congruence, 
so we multiply the 1st congruence by 2^-1 mod 13
```
2^-1 ( 2x  +  5y) ≡ 2^-1 * (6) (mod 13)
       3x  -  7y  ≡          2 (mod 13)
```

```
(2^-1 * 2) * x  +  (2^-1 * 5) y  ≡ (2^-1 * 6) (mod 13)
            3x  -            7y  ≡          2 (mod 13)
```

```
1x  +  (2^-1 * 5) y  ≡ (2^-1 * 6) (mod 13)
3x  -            7y  ≡          2 (mod 13)
```

2^-1 mod 13 = 7 since (2 * 7) mod 13 = 1

```
1x  +  35y  ≡ 42 (mod 13)
3x  -   7y  ≡ 2 (mod 13)
```

reduce terms mod 13
```
1x  +   9y  ≡ 3 (mod 13)
3x  +   6y  ≡ 2 (mod 13)
```

Subtract 3 times the first congrunce from the second congruence
```
1x  +  9y ≡ 3  (mod 13)
0x  - 21y ≡ -7 (mod 13)
```

reduce terms mod 13
```
1x  + 9y ≡ 3  (mod 13)
0x  + 5y ≡ 6 (mod 13)
```

We want the coefficient of the y to be 1 in the second congruence, 
so we multiply the 2nd congruence by 5^-1 mod 13

```
        1x  + 9y  ≡         3  (mod 13)
5^-1 * (0x  + 5y) ≡ 5^-1 * (6) (mod 13)
```

```
1x  + 9y  ≡         3  (mod 13)
0x  + 1y  ≡ (5^-1 * 6) (mod 13)
```

5^-1 mod 13 = 8 since (5 * 8) mod 13 = 1

```
1x  + 9y  ≡  3 (mod 13)
0x  + 1y  ≡ 48 (mod 13)
```

reduce terms mod 13
```
1x  + 9y  ≡ 3 (mod 13)
0x  + 1y  ≡ 9 (mod 13)
```

subtract 9 times the second congruence from the first congruence
```
1x  + 0y  ≡ -78 (mod 13)
0x  + 1y  ≡ 9 (mod 13)
```

reduce terms mod 13
```
1x  + 0y  ≡ 0 (mod 13)
0x  + 1y  ≡ 9 (mod 13)
```

x ≡ 0 (mod 13)
y ≡ 9 (mod 13)

Step 3) check our solution against the original linear congruences
```
2x  +  5y ≡ 6 (mod 13)
3x  -  7y ≡ 2 (mod 13)
```

Plug in x and y
```
0  +  45 ≡ 6 (mod 13)
0  -  63 ≡ 2 (mod 13)
```

reduce terms mod 13
```
6 ≡ 6 (mod 13)
2 ≡ 2 (mod 13)
```
So our solution is consistent with the original linear congruences

Hope this makes sense

Computer science theory

Course: Computer science theory > Unit 2

Modular exponentiation

For example:

What can we do to reduce the size of terms involved and make our calculation faster?

How can we calculate A^B mod C quickly if B is a power of 2 ?

Want to join the conversation?