Question

find the remainder.

Answer 1

\(\large \begin{align} \color{black}{\dfrac{74^{211}}{511}\hspace{.33em}\\~\\}\end{align}\)

Answer 2

i have figured this out , if someone can post a short method than mine, i will fan and medal

Answer 3

\[\begin{cases} ord_{511}(74) = 3\\
211 \equiv 1\ \text{mod } 3 \end{cases} \implies 74^{211} \equiv 74^1\ \text{mod } 3 \]

Answer 4

i really dont know this \(ord\) stuff

Answer 5

does it mean primitive root

Answer 6

No. ord_n(x) is the lowest number (say, m) such that x^m == 1 (mod n)

Answer 7

omg that works

Answer 8

but how did u find that

Answer 9

\(74^3 mod ~~511\) finding it practically by calculation is tedious

Answer 10

for such a large number.

Answer 11

Well, how did you do it? No other common methods seemed like they'd be quick, so I assumed the order was low. I assume your method involved more difficulty than 2 multiplications, or 74*74 and 74*366?

This method will not work if the order is high though. There is a way to find the order quicker, I'll see if I can find it in my notes.

Answer 12

i applied the chineese remainder theorm which was pretty long .

Answer 13

you may use the fact that order is a divisor of phi(n) but i think chinese remainder thm isnt that bad here

Answer 14

but @INewton finded the \(\equiv 1\) quickly by \(ord\)

Answer 15

I was wrong, there's no really quick way to find ord (ny hand - the algorithm I knew is only really practical when programming). There is a quick way to find primitive roots by hand, but that won't help.

For interest, there is another way to do this, with at most 2 * log_2(211) multiplications (but you'd find the order on the way, so in most cases it's less).

It involves writing 211 in binary then using fast exponentiation by squaring. It's how a computer can work out x^(10^100) mod n in seconds, but works well for small paper calculations like this.

Answer 16

once you know \(74^3 \equiv 1 \pmod {511}\), rest is a piece of cake. you will be spending most of the time in finding the order tho

Answer 17

511 is a composite number and i think we shouldnt expect primitive roots for composites as most composites have no primitive roots

Answer 18

Yeah, indeed. Was just noting that because it's what I found in my notes when looking for what I thought was an order finding pen-and-paper method >:(

Answer 19

yeah this is a discrete logarithm problem, one of the hardest out there

Answer 20

\(\large \begin{align} \color{black}{\dfrac{74^{211}}{511}=ar_2x+br_1y\hspace{.33em}\\~\\
ax+by=1\hspace{.33em}\\~\\
511=73\times 7\hspace{.33em}\\~\\
a=73 \hspace{.33em}\\~\\
b=7 \hspace{.33em}\\~\\
73x+7y=1\hspace{.33em}\\~\\
\implies 3x (\mod~~7)=1\hspace{.33em}\\~\\
x=5,y=-52\hspace{.33em}\\~\\
\normalsize \text{so } \hspace{.33em}\\~\\
\dfrac{74^{211}}{511}=73\cdot 5r_2+7\cdot -52r_1\hspace{.33em}\\~\\
\dfrac{74^{211}}{a}=r_1 \hspace{.33em}\\~\\
=\dfrac{74^{211}}{73} \hspace{.33em}\\~\\
=1 \hspace{.33em}\\~\\
r_1=1 \hspace{.33em}\\~\\
\dfrac{74^{211}}{b}=r_2 \hspace{.33em}\\~\\
\dfrac{74^{211}}{7}\hspace{.33em}\\~\\
=\dfrac{4^{211}}{7}\hspace{.33em}\\~\\
=\dfrac{4\cdot (4^{6})^{35}}{7}\hspace{.33em}\\~\\
=4 \hspace{.33em}\\~\\
r_2=4 \hspace{.33em}\\~\\
\dfrac{74^{211}}{511}=73\cdot 5\cdot 4+7\cdot -52\cdot 1\hspace{.33em}\\~\\
=73\cdot 5\cdot 4+7\cdot -52\cdot 1\hspace{.33em}\\~\\
=1460-364 \hspace{.33em}\\~\\
=74 \hspace{.33em}\\~\\
}\end{align}\)


this is my method but too long.

Answer 21

That method is probably more reliable though. Although if I had a question like this, with no obvious method using x^phi(n) == 1 mod(n), I'd probably just exponentiate it by squaring (i.e. calculate 74^2 mod 511, then square it to get 74^4 mod 511, ... get 74^128, then combine the 128 + 64 + 16 + 2 + 1 results. I guess it depends how quickly you can do each step of CRT as to which is faster - unless you run into the order early doing multiplications. I assume, as this is maths and not comp sci, they'd expect your method.

Answer 22

thats smart i should have realized that.

Answer 23

where did you learn this version of CRT ? it looks very interesting xD

Answer 24

this is not actual CRT its application of it and its very easy

Answer 25

it does look easy as you can use euclod gcd alogirthm for solving below\[ax + by=1\]

however it will get messy when you have more than two prime factors

Answer 26

by the way i just realized that \(\dfrac{\phi {(511)}}{2}=216
\)
and
\(74^{216}\equiv 1 (mod ~~ 511)\)

Answer 27

i m being fooled by this question

Answer 28

i can give u statement of this CRT which u can learn easily

Answer 29

keep dividing by 2 till the exponent becomes 27

Answer 30

id like to see it

Answer 31

wait

Answer 32

\(\large \begin{align} \color{black}{\normalsize \text{if a number} N =a\times b \hspace{.33em}\\~\\
\normalsize \text{where a and b are prime to each other ie } \gcd(a,b)=1, \hspace{.33em}\\~\\
\normalsize \text{and M is a number such that } \hspace{.33em}\\~\\
Rem[\dfrac{M}{a}]=r_1 \hspace{.33em}\\~\\
\normalsize \text{and } \hspace{.33em}\\~\\
Rem[\dfrac{M}{b}]=r_2 \hspace{.33em}\\~\\
\normalsize \text{then } \hspace{.33em}\\~\\
Rem[\dfrac{M}{N}]=ar_2x+br_1y \hspace{.33em}\\~\\
\normalsize \text{where } \hspace{.33em}\\~\\
ax+by=1 \hspace{.33em}\\~\\
}\end{align}\)

Answer 33

nice nice i like how this statement avoids refering to inverses directly xD

Answer 34

i did'nt understand why u said " divide by 2 until u get 27"

Answer 35

It is made for people like me.

Answer 36

:) was replying to this
http://gyazo.com/54135c53763f95e8d931746ccaf99d50

Answer 37

since we know that \(74^3 \equiv 1 \pmod {511}\), we have
\[(74^3)^k \equiv 1^k \equiv 1 \pmod {511}\]

Answer 38

i don't think its true.

Answer 39

\(\huge m^{\phi {(n)}}\pmod n\equiv m^{\frac{\phi {(n)}}{2}} \pmod n\equiv 1\)

Answer 40

thats true only when \(m\) is NOT a primitive root

Answer 41

...when m is not a primitive root of n?

Answer 42

thats a good observation btw :)
consider an example : \(m=2 \) and \(n=5\)

\[\large 2^{\phi(5)}\equiv 1 \pmod{5}\]
\[\large 2^{\frac{\phi(5)}{2}}\equiv ? \pmod{5}\]

Answer 43

yes

Answer 44

Also another interesting result is \(\phi(n)\) is always even for \(n\gt 3\)

Answer 45

-1

Answer 46

oh i see

Answer 47

i have another observation when m is a primitive root of n then
\(\large m^{\phi (n)/2} \pmod n=-1\)

Answer 48

thats true for all \(n \ge 3\). we can also say if \(m\) is not a primitive root of \(n\) then
\[\large m^{\phi (n)} \equiv m^{\phi (n)/2} \equiv 1\pmod{n} \]


those observations all follow trivially from the definition of primitive root

Answer 49

too much observations for me

Answer 50

cool stuff =)