- #1

pivoxa15

- 2,259

- 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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter pivoxa15
- Start date

- #1

pivoxa15

- 2,259

- 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,453

- 149

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

pivoxa15

- 2,259

- 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,426

- 4

6+2.40.9+81=6+9=15

- #5

Gokul43201

Staff Emeritus

Science Advisor

Gold Member

- 7,176

- 21

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,426

- 4

Share:

- Last Post

- Replies
- 7

- Views
- 221

- Last Post

- Replies
- 11

- Views
- 304

- Replies
- 10

- Views
- 316

- Replies
- 14

- Views
- 575

- Replies
- 8

- Views
- 425

- Last Post

- Replies
- 3

- Views
- 572

- Last Post

- Replies
- 5

- Views
- 406

- Replies
- 32

- Views
- 633

- Replies
- 11

- Views
- 607

- Last Post

- Replies
- 17

- Views
- 902