Question

find the value of 7^2882 mod 2925 using euler's function i know answer is 49 . but dont know how to figure it out with the euler's function which i need to be able to do

Answer 1

if i recall correctly \(b^{\phi(m)}\equiv 1(m)\)

Answer 2

so i guess the first step is to find \(\phi(m)\) which as i recall we do by finding the prime factorization of \(2925\) and then use the fact that \(\phi\) is multiplicative
stop me if i am on the wrong track

Answer 3

yes i think so trying to figure it out going step by step 1 its awkward though !

Answer 4

\(2925=3^2\times 5^2\times 13\) and so \(\phi(2925)=3\times 2\times 5\times 4\times 12=1440\)

Answer 5

gotta run, but think that is a good start

Answer 6

cheers

Answer 7

Now the 49 is clear right

Answer 8

2882=2×1440+2

Answer 9

quick question how did you get the factors eg 3^2 x 5^2 x 13 at the starts ? i know they add up to 2925 but how do you know the factos ?

Answer 10

i would like to say i factored by hand, but i didn't, i just did this
http://www.wolframalpha.com/input/?i=factor+2925

on the other hand you know it is divisible by 25 because it ends in a 25 and you also know it is divisible by 9 because the digits add up to 18, so it is not too hard to factor, since it must contain \(3^2\) and \(5^2\)

Answer 11

ok cheers

Answer 12

also is it clear how to find \(\phi(3^2\times 5^2\times 13)\) ?

Answer 13

and that we know \(7^{\phi(m)}\equiv 1(m)\) making \(7^{2880}\equiv 1(2925)\)

Answer 14

yesbut what about the 2 ? where does that come into it or how did i get 49