Question

2^122(mod77)

Answer 1

There's gotta be an easier way of doing this than what I was trying to do......

Answer 2

what have you been trying ?

Answer 3

nice problem :)

Answer 4

The only sort of shortcut I used that helps at all is the idea that \[a^{p-1} = 1(modp)\] (however you do the congruent symbol thingy). But that doesnt reduce the power enough for me to know an easy way of working it.

Answer 5

u wanna find set of residues ?

Answer 6

it works only when p is prime right ?

Answer 7

\(\cong\) \cong

Answer 8

Probably, lol. But this was an exam and I was under pressure :D

Answer 9

I are is go dumb on exam x_o

Answer 10

Phi function works better hehe
oh lol u wanna find only mod :)
its easy :P

Answer 11

Okay, so how does phi function relate to this? I thought phi function was to find the order?

Answer 12

a^(phi 77) = 1 mod 77

Answer 13

^^

Answer 14

Havent seen that one, lol.

Answer 15

seen chinese remainder theorem ?

Answer 16

Okay:
\[\phi(77) = (7^{1} - 7^{0})(11^{1}-11^{0}) = (6)(10) = 60\]
And nope, never heard of it.

Answer 17

2^10= 1 mod 7
2^6 = 1 mod 11

2^60= 1 mod 7
2^60= 1 mod 11

2^60 = 1 mod 77

Answer 18

Thats kinda sad....All I had to do is a^(phi77)? :( Why hadn't I ever seen that before ._.

Answer 19

it goes by name : "euler theorem"

Answer 20

I wasnt trying to be rude by not calling it by name, im sorry.

Answer 21

hehe u can use it any where :P
phi function , or just use euler like this which u already know

2^10= 1 mod 7
2^6 = 1 mod 11

2^60= 1 mod 7
2^60= 1 mod 11

2^60 = 1 mod 77

Answer 22

nice :)

Answer 23

hmm lol u took abstract before number theory ?

Answer 24

i think this is why u dint hear of it

Answer 25

No, I havent taken number theory. But our professor brings up the class a lot, so I think he kind of assumes we have taken it.

Answer 26

But yeah, I hadn't ever seen the phi function used in that context. Id only used it to determine the amount of elements in U(n) (thats the notation our professor uses for it).

Answer 27

i see , hmm when i come back home , i'll send u review for number theory that u need in abstract , u wont understand anything in abstract without them :)

Answer 28

you could also use \(\large a^{p-1}\equiv 1\pmod p\). see ikram's reply above...

\(2^{7-1}\equiv 1\pmod 7\implies 2^6\equiv 1\pmod 7 \implies (2^6)^{10}\equiv 1^{10 }\pmod{7}\)

Answer 29

similarly work mod11 and combine

Answer 30

Oh, you can multiply them?!?!

Answer 31

or wait , here review first part

https://drive.google.com/file/d/0B1oczGnMVhNqS3JRWkhvalVfOUE/view?usp=sharing

Answer 32

\(\large x\equiv a \pmod{ p_1}\)
\(\large x\equiv a \pmod{ p_2}\)

\(\large x\equiv a\pmod{p_1\times p_2}\)

Answer 33

So wait, how would that look then?
[\(2^{122}\ (mod7)\)]* [\(2^{122}(mod11)\)]

Answer 34

no we cant multiply like that

Answer 35

\(\large a\pmod{p_1p_2} \not\equiv a\pmod{p_1}\times a\pmod{p_2}\)

Answer 36

\(\large 2^{60}\equiv 1\pmod{7}\)
\(\large 2^{60}\equiv 1\pmod{11}\)

\(\large\implies 2^{60}\equiv 1\pmod{7\times 11}\)
\(\large\implies \left(2^{60}\right)^2\equiv 1^2\pmod{7\times 11}\)
\(\large \implies \cdots \)

Answer 37

I see. I think I get what you mean. That just makes the answer 4 basically x_x

Gah, I gotta figure out how you use the math latex in that way, making text big and typing it out so fast, lol.

Answer 38

are you still using equation editor or writing code by hand ?

Answer 39

Well, Ive learned a little bit how to do it by hand, but Im slow at it. I need to get used to doing it by hand because if you use the equation editor it just forces your text to another line, which is annoying.

Answer 40

And thanks for the help everyone. Just disappointing because I didnt expect to be shown all these things I didn't know, I thought there was just an easier way I wasn't thinking of while doing this on the exam. But this stuff I don't have in notes or anything. Meh, lol. I appreciate everyone's input ^_^

Answer 41

And you can continue, Ganeshie, I just wanted to thank everyone

Answer 42

http://www.codecogs.com/latex/eqneditor.php

Answer 43

Oh wow. So you can type it up in there and copy and paste or something, ikram?

Answer 44

np :) i was just gona say that euler theorem makes your life simple... but you can always reduce the power manually... it can be a little painful though

Answer 45

Yeah, I did it manually, but I also applied that one theorem incorrectly. I was on an exam, so it didnt even occur to me that the fermat theorem only works for prime numbers. Apart from that, I never knew the phi function did that, only used it for finding the order of U(n). I guess I just wish that stuff was in my lecture notes.

Answer 46

Oh i see "p" almost always refers to prime number in NT

Answer 47

\(\large 2^{122}\equiv 2^{6\times 20+2} \equiv 4(64)^{20} \equiv 4(13)^{20 }\equiv \cdots \)

Answer 48

that reduction always works if u don't remeber any theorems ^^

Answer 49

u need to learn these shortcuts in Abstract algebra instead of reducing power , u wont have time to reduce anything since its not number theory
some of question give this part as u need to know answer in 30 sec
to solve something else ( just advice )

Answer 50

Wait, that next step goes down to \(4(13)^{20}\) when modding by 77? I could see that if it were backwards and you had 77 mod 64.

Answer 51

Yeah, this was a question that expected a quick answer, not only based on the amount of room on the paper we had to do the problem, but how many other problems there were. The problems I was taking forever on clearly needed to be done in a minute or two. Which would lead me to my next question xD

Answer 52

it should be : \[2^{122}\equiv 2^{6\times 20+2} \equiv 4(64)^{20} \equiv 4(-13)^{20 }\equiv \cdots\]

Answer 53

because \(\large 64 \equiv -13 \)