Modulo reduction problem

  • Thread starter scottstapp
  • Start date
  • #1
scottstapp
40
0

Homework Statement



Reduce 34567 modulo 19.

Homework Equations





The Attempt at a Solution


I approached by first reducing 4567 modulo 18.

I got the following: 34567= 318*253+13=(318)253*313 congruent to 12531594323 congruent to 14 mod 19

Is this the correct approach? I am not sure where 14 came from in the end I just guess and checked until I found a value that worked which was 14. Any explanations on how to correctly find 14?
 

Answers and Replies

  • #2
Tinyboss
244
0
You were exactly right to use Fermat's Little Theorem to show that 34567 = 313 mod 19. From there I'd use binary exponentiation: 313 = 38+4+1 = 3834*3.

So mod 19, 34 = 5, so then 38 = 3434 = 25 mod 19 = 6 mod 19.

Put it together: 3834*3 = 6*5*3 mod 19 = 90 mod 19 = 14.
 

Suggested for: Modulo reduction problem

Replies
3
Views
435
Replies
1
Views
461
  • Last Post
Replies
2
Views
738
Replies
3
Views
667
  • Last Post
Replies
13
Views
440
  • Last Post
Replies
4
Views
299
  • Last Post
Replies
23
Views
534
Replies
2
Views
125
Replies
5
Views
117
Replies
5
Views
335
Top