- #1

- 2,255

- 1

a^(phi(m)) is congruent to 1 (mod m)

The question is calculate

7^40002 mod 1000

I could only reduce it to

7^402 mod 1000

What should I do now?

Thanks

- Thread starter pivoxa15
- Start date

- #1

- 2,255

- 1

a^(phi(m)) is congruent to 1 (mod m)

The question is calculate

7^40002 mod 1000

I could only reduce it to

7^402 mod 1000

What should I do now?

Thanks

- #2

lurflurf

Homework Helper

- 2,432

- 132

Again with the vague theorem referrence. This time you clearly mean Eulers Totient Theorem. Why not reduce once more?pivoxa15 said:

a^(phi(m)) is congruent to 1 (mod m)

The question is calculate

7^40002 mod 1000

I could only reduce it to

7^402 mod 1000

What should I do now?

Thanks

we have 7 relatively prime to 1000.

phi(1000)=1000-1000/2-1000/5+1000/10=1100-700=400

so (all mod 1000)

7^400=1

7^40002=((7^400)^100)(7^2)=(1^100)(7^2)=7^2=49

- #3

- 2,255

- 1

11^100 (mod 72)

This time I reduced it to 11^4 (mod 72)

I could evaluate it by hand which works out to be 7^4 (mod 72) but is there a better way of doing it.

Thanks

- #4

matt grime

Science Advisor

Homework Helper

- 9,395

- 3

6+2.40.9+81=6+9=15

- #5

Gokul43201

Staff Emeritus

Science Advisor

Gold Member

- 7,051

- 18

Wait a minute :

11^4 = 121^2 == (-23)^2 = 529 =(72*7) + 25

So, 11^4 == 25 (mod 72)....no?

11^4 = 121^2 == (-23)^2 = 529 =(72*7) + 25

So, 11^4 == 25 (mod 72)....no?

- #6

matt grime

Science Advisor

Homework Helper

- 9,395

- 3

- Last Post

- Replies
- 2

- Views
- 915

- Last Post

- Replies
- 7

- Views
- 1K

- Last Post

- Replies
- 5

- Views
- 1K

- Last Post

- Replies
- 3

- Views
- 879

- Last Post

- Replies
- 9

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 741

- Last Post

- Replies
- 2

- Views
- 1K

- Replies
- 0

- Views
- 2K

- Last Post

- Replies
- 6

- Views
- 925