What is the remainder when 4 5 2 3 is divided by 7?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Good eye for spotting 3 3 ≡ − 1 ( m o d 7 ) .
4 5 ≡ 3 ( m o d 7 )
4 5 2 ≡ 2 ( m o d 7 )
4 5 4 ≡ 4 ( m o d 7 )
4 5 5 ≡ 5 ( m o d 7 ) from 1 and 3
4 5 6 ≡ 1 ( m o d 7 ) from 1 and 4
4 5 1 8 ≡ 1 ( m o d 7 )
4 5 2 3 ≡ 5 ( m o d 7 ) from 4 and 6
hence the answer is 5
This works too!
Systematic approach:
By Fermat, 4 5 2 3 ≡ 3 2 3 ≡ 3 2 3 m o d 6 ≡ 3 − 1 ( m o d 7 )
We use Extended Euclidean Algorithm to find the modular inverse of 3 modulo 7 (it exists since g cd ( 3 , 7 ) = 1 ). So,
z ≡ 3 − 1 ( m o d 7 ) ⟹ 3 z ≡ 1 ( m o d 7 ) ⟹ z ≡ 5 ( m o d 7 )
We used the following result from the Extended Euclidean Algorithm to get our answer:
g cd ( 3 , 7 ) = 1 = 5 × 3 + ( − 2 ) × 7
Log in to reply
It's not necessarily to invoke Extended Euclidean Algorithm (all the time!). You could just have … ≡ 3 2 3 m o d 6 ≡ 3 5 ≡ ( 3 2 ) 2 ⋅ 3 ≡ 2 2 ⋅ 3 ≡ 5 . Unless you know that 1 = 5 × 3 − 2 × 7 at the back of your head, it's not much easier. Your "systematic approach" is much difficult compared to the purely Fermat's Little Theorem approach.
Log in to reply
Well, everyone has their own preferences.
Log in to reply
@Prasun Biswas – It's just 3 − 1 ≡ 3 1 ≡ 3 − 6 ≡ − 2 ≡ 5 ( m o d 7 ) or to make it more clear we have 3x\equiv 1\equiv -6\stackrel{:3}\iff x\equiv -2\equiv 5 mod 7 , which is just another way of writing it. I really much prefer this to Extended Euclidean Algorithm.
i dont know the concept of mod can you explain it a little bit..
Log in to reply
https://brilliant.org/math/number-theory/modular-arithmetic/
3 ⋅ 4 5 2 3 ≡ 3 ⋅ 3 2 3 ≡ Fermat 3 2 4 ( m o d 6 ) ≡ 3 0
\equiv 1\equiv -6\stackrel{:3}\iff 45^{23}\equiv -2\equiv 5 mod 7 .
Or written in another way
4 5 2 3 ≡ 3 2 3 ≡ 3 2 3 ( m o d 6 ) ≡ 3 − 1
≡ 3 1 ≡ 3 − 6 ≡ − 2 ≡ 5 mod 7 .
4 5 2 3 ≡ ( 4 2 + 3 ) 2 3 ( m o d 7 ) ≡ 3 2 3 ( m o d 7 ) ≡ 9 1 1 ˙ 3 ( m o d 7 ) ≡ 3 ˙ 2 1 1 ( m o d 7 ) ≡ 3 ˙ 2 2 ˙ 8 3 ( m o d 7 ) ≡ 3 ˙ 2 2 ˙ 1 ( m o d 7 ) ≡ 1 2 ( m o d 7 ) ≡ 5 ( m o d 7 )
You could simplify you solution by a bit. Hint: Fermat.
45^6=1 (mod 7),¨fermat. 45 = 3 (mod 7) ,
( 45^ 6 ) 3 * 45 ^ 5 = a mod 7.
(1 ) ^ 3 * (3) ^ 5 = a mod 7.....
243 = 5 mod 7
a = 5 the remainder
Problem Loading...
Note Loading...
Set Loading...
4 5 2 3 ≡ 3 2 3 = ( 3 3 ) 7 ⋅ 3 2 ≡ ( − 1 ) 7 ⋅ 2 = − 2 ≡ 5 ( m o d 7 )