How can i calculate 2741

How can I calculate 2741 mod 77 as simple as possible?
I already know that 2760 mod 77=1 because of Euler’s theorem:
aϕ(n) mod n=1
and
ϕ(77)=ϕ(7⋅11)=(7−1)⋅(11−1)=60
I also know from using modular exponentiation that 2710mod 77=1 and thus
2741 mod 77=2710⋅2710⋅2710⋅2710⋅271 mod 77=1⋅1⋅1⋅1⋅27=27
But can I derive the result of 2741 mod 77 using 2760 mod 77=1 somehow?
by using Euler'stheorem / Fermat's theorem on each of the primes separately. You know that 2710≡1mod11, and you can also see that modulo 7, 27≡−1mod7, so 2710≡(−1)10≡1mod7 as well. So 2710≡1mod77, and 2741=2740+1≡27mod77. (We've effectively found the order of 27 as 10, but a more mechanical procedure may be to use that 2741≡27≡5mod11 and 276≡1mod7 to see that 2741=2742−1≡27−1≡−1mod7, and put 5 mod 11 and -1 mod 7together to get 27.)

2. Euler’s Phi Function. The number of units (invertible elements)
in Zm is equal to the number of positive integers not greater than and
relatively prime to m, i.e., the number of integers a such that 1 · a · m
and gcd(a,m) = 1. That number is given by the so called Euler’s phi
function:
Á(m) = number of positive integers not greater than m
and relatively prime to m.
Forinstance, the positive integers not greater than and relatively prime
to 15 are: 1, 2, 4, 7, 8, 11, 13, 14, hence Á(15) = 8.
We have the following results:
(1) If p is a prime number and s ¸ 1, then Á(ps) = ps − ps−1 =
ps(1 − 1/p). In particular Á(p) = p − 1.
(2) If m1, m2 are two relatively prime positive integers, then Á(m1m2) =
Á(m1) Á(m2).1
(3) If m = ps1
1 ps2
2 . . . psk
k , wherethe pk are prime and the sk are
positive, then
Á(m) = m(1 − 1/p1) (1 − 1/p2) . . . (1 − 1/pk) .
1A function f(x) of positive integers such that gcd(a, b) = 1 ) f(ab) = f(a)f(b)
is called multiplicative.
MODULAR ARITHMETIC 5
For instance
Á(15) = Á(3 · 5) = Á(3) · Á(5) = (3 − 1) · (5 − 1) = 2 · 4 = 8 .
3. Euler’s Theorem. If a and m are two relatively prime positive
integers, m ¸ 2, thenaÁ(m) ´ 1 (mod m) .
The particular case in which m is a prime number p, Euler’s theorem
is called Fermat’s Little Theorem:
ap−1 ´ 1 (mod p) .
For instance, if a = 2 and p = 7, then we have, in fact, 27−1 = 26 =
64 = 1 + 9 · 7 ´ 1 (mod 7).
A consequence of Euler’s Theorem is the following. If gcd(a,m) = 1
then
x ´ y (mod Á(m)) ) ax ´ ay (mod m) .
Consequently, the following function iswell defined:
Z¤
m × ZÁ(m) ! Z¤
m
([a]m, [x]Á(m)) 7! [ax]m
Hence, we can compute powers modulo m in the following way:
an = an mod Á(m) (mod m) ,
if gcd(a,m) = 1. For instance:
39734888 mod 100 = 39734888 mod Á(100) mod 100
= 39734888 mod 40 mod 100 = 38 mod 100 = 6561 mod 100 = 61 .
Fermat’s Little Theorem can be used as test of primality, or rather as
test of non-primality. Example:Prove that 716311796279 is not prime.
Answer: We have that2
2716311796279−1 = 2716311796278 ´ 127835156517 (mod 716311796279) .
But if 716311796279 were prime, 2716311796279−1 would be congruent to
1 modulo m. Warning: Note that am−1 ´ 1 (mod m) does not imply
that m is prime; the only thing that we can say is that if am−1 6´ 1
(mod m) (and gcd(a,m) = 1) then m is not prime.
2Given a power ax,there is an efficient method (easy to implement as an algorithm)
to reduce ax modulo m.

2. Euler’s Phi Function. The number of units (invertible elements)
in Zm is equal to the number of positive integers not greater than and
relatively prime to m, i.e., the number of integers a such that 1 · a · m
and gcd(a,m) = 1. That number is given by the so called Euler’s phi
function:
Á(m) = numberof positive integers not greater than m
and relatively prime to m.
For instance, the positive integers not greater than and relatively prime
to 15 are: 1, 2, 4, 7, 8, 11, 13, 14, hence Á(15) = 8.
We have the following results:
(1) If p is a prime number and s ¸ 1, then Á(ps) = ps − ps−1 =
ps(1 − 1/p). In particular Á(p) = p − 1.
(2) If m1, m2 are two relatively prime positive integers,...