find $\large\tt \color{black}{7^{123} (mod~~ 10)}$ using eulers theorm

Question

accessdenied · Answer

Have you tried anything with this so far?  I am not completely familiar with this but I think I found a workable solution...

mathmath333 · Answer

i can find in general way ,i dont know how to use euler theorm

accessdenied · Answer

The statement of the theorem is that:
  If n and a are coprime, then
     $ a^{\phi(n)} \equiv 1  \ (\text{mod} \ n) $
What I am thinking is that, in our problem we are working with mod 10, so n = 10.  And a = 7 clearly.  So 7 and 10 are coprime, and the theorem applies.
Now, $ \phi (10) = \phi (2*5) = (2 - 1)(5 - 1) = 4 $, and we have:
    $7^{4} \equiv 1 \ (\text{mod} \ 10) $
Does that all make sense?

accessdenied · Answer

From that point, I figure we can rewrite $7^{123} = 7^{4n + r} = 7^{4n} 7^r $, and cancel out the $7^{4n} $ part as multiplication by 1.  The remaining $7^r$ should be much easier to take the mod of!

mathmath333 · Answer

ok 7 and 10 are co prime ,how did u find that empty set (10),
what if n=11

mathmath333 · Answer

empty set=11-1=10 ?

accessdenied · Answer

Oh, $ \phi (n) $ is meant to be the Euler totient function.  Basically it is a count of all positive numbers less than n that are relatively prime to n.  You could count them directly:   1, 3, 7, 9  (so phi(10) = 4).  That trick I used I saw earlier and is basically using two facts:  $ \phi (nm) = \phi (n) \phi (m)$  and $\phi (p) = p - 1$ for a prime p.

accessdenied · Answer

I have to go for now, sorry! There is a good example similar to this problem on the wiki page. "The theorem may be used to easily reduce large powers modulo n. ..." http://en.wikipedia.org/wiki/Euler's_theorem And more about the Euler totient function: http://en.wikipedia.org/wiki/Euler's_totient_function If you need more assistance, definitely bump the question! Good luck!

mathmath333 · Answer

i got the formula of emptyset(n) for any n|N

$\large\tt \color{black}{\large\tt \color{black}{\emptyset(n)=n[(1-\dfrac{1}{x})(1-\dfrac{1}{y}......]}}$

where x ,y,,,,, are prime factors

mathmath333 · Answer

thanks very much for your help

accessdenied · Answer

It isn't actually the empty set symbol, this is the greek letter phi:  $ \phi $.   It represents the Euler totient function or Euler phi function.
Although in LaTeX it defaults to that display with \phi, but it can also show up as this:  $ \varphi $ using \varphi.  Maybe that's what mixed you up there!

If I use that phi:
  $ \large a^{\varphi (n)} \equiv 1 \ (\text{mod} \ n) $

mathmath333 · Answer

ok thanks though

accessdenied · Answer

Glad to help!  :)