Some number theory questions:

.E_C_K_S.

Hi lads I just have a few number theory questions.

How many invertible elements are in Z-63?
Is there a formula for this? If I know a method I will try apply it.

Compute 5^2011 mod 77.
Our lecturer did some of these out but he skips a few steps. Again is there a formula?

Find the solutions of x^3 + 2x^2 -x + 47 = 0 (mod 343)
I know 343 is 7x49 so I find them for 7 and 'lift' to 49 but then I'm not sure where to go to get mod(343)

Thanks!

LeixlipRed

a is invertible mod n if and only if the gcd of a and n is equal to 1. That give you any clues about the first one?

click_here!!!

I think you use the Euler-phi function for the first one. http://en.wikipedia.org/wiki/Euler's_totient_function

You can use the Euler-Fermat theorem for the second one. http://en.wikipedia.org/wiki/Euler's_theorem

Both are described on Wikipedia.

You can check to see if your answer is correct on http://www.wolframalpha.com.

Hope this helps.

.E_C_K_S.

OK so the first one I got 36. Broke it up into 7x9 and then they have 6X6 elements coprime. I presume that is ok?

Second question I get 5^61=5(mod77).Not sure if this is right!

Any idea for the third. I know it will be long but I have no time! Once I get mod7 and then mod49 how do I go from there thanks.

.E_C_K_S.

Just have to bump this lads because my exam is tomorrow!:o

click_here!!!

I think you're right about the first two, but I don't know how to do the other one myself.

If you find out and have spare time, let me know! Thanks.

MoogPoo

Compute 5^2011 mod 77.

Using Euler's I got e(77) = 60
SO 5^60 = 1mod77

so I wrote 2011 = 60(33) + 31

that means you can keep subtracting 60 from 2011 till you get 31
and so 5^2011 = 5^31 mod77. I think thats right how did you do it? I might be wrong

Then I dunno how to simplify it more.
This is a complete guess cause I got answer from wolframalpha.

Can you say by Fermat's that 5^31 = 5mod7 and 5^31 = 5mod11
and then try and find x = 5mod7 and x = 5mod11 by Chinese Remainder or something. So x = 5, this is the answer on wolfram anyway.

click_here!!!

[latex]5^{2011} \bmod{77} \equiv 5^{2011 \bmod{\phi(77)}}[/latex]
[latex]\equiv 5^{2011 \bmod{60}}[/latex] (Since [latex]5^{1980}.5^{31} \equiv 5^{2011} \bmod{77}[/latex] (Read the Wikipedia article on Modular exponentiation))


2011 mod 60 = 31
[latex]5^{2011} \bmod{77} \equiv 5^{31} \bmod{77}[/latex]

To calculate [latex]5^{31} \bmod{77}[/latex] on your calculator:
Since 5^{31} is too big to display on most calculators, split your equation into terms like 5^3 and 5^4 which can be displayed on your calculator like so:
[latex]5^{31} = (5^4)^7.(5^3)[/latex]

Then, calculate each of these terms mod 77:
For example, to calculate [latex]5^3 \bmod{77}[/latex], do [latex]5^{3} \div 77[/latex] on your calculator. Then subtract the integer part so you're left with the fraction bit. (0.6233766233766233766233766233766233766233766233766233766233...)
Then multiply by 77.

Now solve this:
[latex]\equiv (5^4 \bmod{77})^7.(5^3 \bmod{77}) \bmod{77}[/latex]

Tip: for an easier example, look at Wikipedia's example of 7^222 mod 10 on the Euler-Fermat theorem article.

MoogPoo

yeah i was trying the calculator way alright but it seems messy and i might mess it.
if 5^2001 = 5^31 mod 77 = a mod 77
then can't you solve for x = a mod 77
by Fermats
x = 5 mod 7
x = 5 mod 11

then use Chinese RT
x = 5 mod 7
x = 5 mod 11
and solve for x and get 5
then if y a solution y = x = 5?

Eliot Rosewater

click_here!!! wrote: »

Tip: for an easier example, look at Wikipedia's example of 7^222 mod 10 on the Euler-Fermat theorem article.

If WALSHY16291 gets a tough question in the exam will he be able to ask the invigilator for access to Wikipedia so he do the easier version?


The solution to this particular example involves considering 5^2011 seperately in mod 7 and mod 11.

As MoogPoo says, you get x = 5 mod 7 and x = 5 mod 11, but it's not neccesary to use CRT at all. x=a (mod n), x=a (mod m), n & m co-prime, implies x=a (mod nm).

.E_C_K_S.

I was wondering when you would reply!:D For the q4 that he gave us on the sample test, I broke 343 into 7^3 but I'm unsure what formula to use for this since we have only used squares in the examples?

Thanks for the replies lads!