Question

This one as really got me foxed! The book I'm looking at says you use another form of the FLT
If x^(p-1) not = 1 mod p then p is not prime. Then it asks you to show that 66,013 is not prime. Such a big number and I find modular arithmetic pretty difficult!

Answer 1

I can understand how you could prove it for say 39.
We would show that 2^38 NOT = 1 mod 39 and make the arithmetic easier by writing
2^38 = 2^36 . 2^2.

Answer 2

i guess you could start by writing

2^66012 = 6^65536 . 2^256.2^128.2^64.2^16.2^12 mod 66013

but you would need a big number crunching computer to work that out!!

Answer 3

the last 5 expressions could be handled by a good on-line calculator I guess.

Answer 4

im sorry i cant get the answer it keeps going in to a error breakdown'

Answer 5

and you would use the relation rs mod p = r mod p * s mod p

Answer 6

you using a calculator?

Answer 7

yes'

Answer 8

you can get a value for 2^32 mod 66013 using a calculator which is 497

the to get 2^64 you square 497 the repeat to process of finding the remainder

Answer 9

2^65536 is the problem

Answer 10

you might be able to simplify that using mod arithmetic Ill have to hit the books, i guess

Answer 11

wow!!!

Answer 12

That is this:
2^65536

Answer 13

how did you get that?

Answer 14

This server has 1152 cores, I borrowed 1 to do the calculation lol

Answer 15

Something tells me you probably didn't want that massive number though xD

Answer 16

now we need to divide that by 66013 and find the remainder

Answer 17

lol no!

Answer 18

Oh boy, well I gotta run to the bank, can you wait a moment? LOL

Answer 19

By this server I meant the QC server xD

Answer 20

there must be an easier way to do this!!!!

Answer 21

Probably xD

Answer 22

Hero messaged me asking what the textbook was, Maybe he has some ideas

Answer 23

talk to you later

Answer 24

reckon there is a brute-force way to do it which doesn't crash the calculator

You can factor: \(66012 = 2^2 * 3 * 5501\)


\(\implies 2^{66012} = 2^{4 * 3 * 5501} = \left (2^{ 5501}\right)^{12}\)

Converting to binary: \(5501 \equiv {1010101111101}_2\)

so \(5501 = 2^0 + 2^2 + 2^ 3 + 2^ 4 + 2^ 5 + 2^ 6 + 2^8 + 2^{10} + 2^{12}\)

IE:

\( 2^{5501} = 2^{2^0 + 2^2 + 2^ 3 + 2^ 4 + 2^ 5 + 2^ 6 + 2^8 + 2^{10} + 2^{12}}\)

\( = 2 * 2^4 * 2^8 * 2^{ 16} * 2^{32} * 2^{ 64} * 2^{ 256} * 2^{ 1024} * 2^{ 4096}\)


The mod of the product is the product of the mods, simple ones first:

\(2 \mod 66013 = 2 \)

\(2 ^4 \mod 66013 = 16 \)

\(2 ^8 \mod 66013 = 256 \)


if you work through all of that meticulously, remembering that \(a^k = \alpha ^ k \mod m\) and \(ab = \alpha \beta \mod m\), i think you can grind out a result.

the site is already slooooooow so those previous posts do not help

Answer 25

"slooooooow" But the site is fast ._.

Answer 26

if it's slow it's client side ._.

Answer 27

Oh yea, latex does take a while to start loading... I really need to work on ways to fix that, such as pre-loading the extensions and such...

Answer 28

I thought you were talking about the site, not LaTeX

Answer 29

There, after some work, mathjax now idly pre-loads assets for mathml upon page load, and instead of queuing latex to be loaded, i made it forcefully load the content, so as a result, LaTeX should now load faster

Answer 30

still takes about 5-10 seconds to finish loading mathml in the background, I'll need to figure out why and fix that at some point however

Answer 31

there we go :P

Answer 32

Fast enough for you now? @sillybilly123

Answer 33

(you might need to clear your cache)

Answer 34

thx U, i think you might be right 😊

celtic: there is an easy way to factor 66013. Fermat's factorization method

http://openstudy.com/updates/56ae016be4b0da09eb82f8c0

in fact that was asking the exact same question i think.

Answer 35

yea Tanks billy. However they wanted you to use FLT.
i finally used brute force and showed that it was not = 1 mod 66013.

I found 2^65536 by repeating the calculation 2^256 --> 2^512 up to 2^65536

Answer 36

i had to use the WEb 2 online calculator which can handle very large numbers

Answer 37

Yeah Fermat's Factorization is much easier!