• Support PF! Buy your school textbooks, materials and every day products Here!

Modulo reduction problem

  • Thread starter scottstapp
  • Start date
  • #1
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
236
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.
 

Related Threads for: Modulo reduction problem

  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
2
Views
517
  • Last Post
Replies
1
Views
7K
  • Last Post
Replies
1
Views
786
  • Last Post
Replies
8
Views
896
Replies
6
Views
4K
  • Last Post
Replies
3
Views
10K
  • Last Post
Replies
3
Views
1K
Top