Modular mathematics - what is 7^(-1) mod 10

[Woolyabyss]

Sorry,
This isn't a homework question. I'm just having trouble understanding some of the notes I've taken down.I'd really appreciate if some of you could help me understand this.
________________

1/3 is that number with the property

(1/3)(3) = 1
...

what is 7^(-1) mod 10?

7^(-1) ≡ 3 mod 10

because 7 * 3 ≡ 1 {21 - 2(10)= 1}
____________

Is it ≡ to 3 because 7 by 3 gives you 1 like in the case of 1/3.

but I'm not multiplying 7^(-1) by 3?

If someone could help me understand this it would be really appreciated.

 

[nrqed]

Sorry,
This isn't a homework question. I'm just having trouble understanding some of the notes I've taken down.I'd really appreciate if some of you could help me understand this.
________________

1/3 is that number with the property

(1/3)(3) = 1
...

what is 7^(-1) mod 10?

7^(-1) ≡ 3 mod 10

because 7 * 3 ≡ 1 {21 - 2(10)= 1}
____________

Is it ≡ to 3 because 7 by 3 gives you 1 like in the case of 1/3.

but I'm not multiplying 7^(-1) by 3?

If someone could help me understand this it would be really appreciated.

Well, the explanation depends on what you want to use a starting point. If you want to start from the answer, $7^{-1} ≡ 3 mod 10$ and just check that it is correct, it is quick. We just multiply both sides and check if they are equal, modulo 10. The left side is $7 \times 7^{-1} =1$
and the right side is 7 x 3 = 21 which is indeed 1 modulo 10. So that checks out.

Now, let's say we did not know the answer. Then we could start with

$$7 \times \frac{1}{7} =1 \text{ mod } 10$$
We want an integer value for $1/7$ modulo 10 and of course it won't work if we use 1 as the right hand side. So we now try the next possibility for 1 mod 10, which is 11. So we have

$$7 \times \frac{1}{7} = 11 \text{ mod } 10$$

Again, we get a non integer solution. We try the next possibility for 1 mod 10, which is 21. So now we have

$$7 \times \frac{1}{7} = 21 \text{ mod } 10$$

and we get

$$\frac{1}{7} = 3 \text{ mod } 10$$

 

[Woolyabyss]

Well, the explanation depends on what you want to use a starting point. If you want to start from the answer, $7^{-1} ≡ 3 mod 10$ and just check that it is correct, it is quick. We just multiply both sides and check if they are equal, modulo 10. The left side is $7 \times 7^{-1} =1$
and the right side is 7 x 3 = 21 which is indeed 1 modulo 10. So that checks out.

Now, let's say we did not know the answer. Then we could start with

$$7 \times \frac{1}{7} =1 \text{ mod } 10$$
We want an integer value for $1/7$ modulo 10 and of course it won't work if we use 1 as the right hand side. So we now try the next possibility for 1 mod 10, which is 11. So we have

$$7 \times \frac{1}{7} = 11 \text{ mod } 10$$

Again, we get a non integer solution. We try the next possibility for 1 mod 10, which is 21. So now we have

$$7 \times \frac{1}{7} = 21 \text{ mod } 10$$

and we get

$$\frac{1}{7} = 3 \text{ mod } 10$$

Thanks, I understand it a lot better now.

 

[ehild]

To check if 7^-1=3 mod 10, apply modular arithmetic when multiplying i with 7:

3(mod 10) x 7(mod 10) =1 mod 10 ehild

 

[HallsofIvy]

Another way of doing it: if x= 7^-1 (mod 10) then 7x= 1 (mod 10). Now you could try x= 0 to 9 to see which works.

Or you could write 7x= 1+ 10n for some integer n. That is the same as 7x- 10n= 1, a "Diophantine" equation.

Use the "Euclidean algorithm" to solve that equation-
7 divides into 10 once, with remainder 3: 10- 1(7)= 3.
3 divides into 7 twice, with remainder 1: 7- 2(3)= 1.

Replace that "3" with "10- 7" from the previous equation: 7- 2(10- 7)= 3(7)- 2(10)= 1.

So one solution to 7x- 10n= 1 is x= 3, n= 2 which tells us that 3(7)= 1 (mod 10) and that 7^-1= 3 (mod 10).

 

[Woolyabyss]

Another way of doing it: if x= 7^-1 (mod 10) then 7x= 1 (mod 10). Now you could try x= 0 to 9 to see which works.

Or you could write 7x= 1+ 10n for some integer n. That is the same as 7x- 10n= 1, a "Diophantine" equation.

Use the "Euclidean algorithm" to solve that equation-
7 divides into 10 once, with remainder 3: 10- 1(7)= 3.
3 divides into 7 twice, with remainder 1: 7- 2(3)= 1.

Replace that "3" with "10- 7" from the previous equation: 7- 2(10- 7)= 3(7)- 2(10)= 1.

So one solution to 7x- 10n= 1 is x= 3, n= 2 which tells us that 3(7)= 1 (mod 10) and that 7^-1= 3 (mod 10).

Thanks, my lecturer just showed us this method today.