Question

Prove/Disprove

\(\large 2^{p − 1} \equiv 1 \mod p^2\) has no solutions

\(p\) is a prime number

Answer 1

:)

Answer 2

I am not able to find solutions for your first equation itself haha! looks the proof would be interesting xD

Answer 3

I agree, it's a fairly mind-boggling equation :P

Answer 4

hmm

2^p-1=1 mod p^2
lets assume it has a solution ,

then 2^(p-1/2)= 1 mod p

hmm lets see any contradiction

Answer 5

So, basically, \(\large p=\frac{1}{2}\)

Answer 6

no there is not such a thing , im looking for Elulers criterion
it should contradict this thing , but not sure if we can apply 2

Answer 7

only found primitive root :(

Answer 8

if it helps, there are no solutions for the first 1000 primes :
http://primes.utm.edu/lists/small/1000.txt

Answer 9

however the equation \(\large \color{Red}{3}^{p − 1} \equiv 1 \mod p^2\) has a solution : \(\large p = 11\)

Answer 10

http://www.wolframalpha.com/input/?i=%283%5E%2811-1%29-1%29+mod+11%5E2

Answer 11

brb...

Answer 12

not in general , it says :-
if p is an odd prime then there exist a primitive root of p , such that
\(r^p-1 \neq 1 \mod p^2\)

hmm idk for 2 :(

Answer 13

ok lol

Answer 14

i just read it

for k>=3 the integer 2^k has no primitive roots :3

done

Answer 15

@ganeshie8 how did you check 1000 numbers ?

Answer 16

http://ideone.com/a1fgEh

scroll down

Answer 17

that shows remainders : \(\large (2^{p-1}-1) \mod p^2\)

Answer 18

could use that number theory thingy, let me grab my book

Answer 19

sure :) i have exhausted all the trials... not getting any new ideas >.<

Answer 20

ok so could we show that \(2^{p-1}\) is not relatively prime since 1 isn't a prime? and so 1 will always go into p^2?

Answer 21

so it fails the requirement?

Answer 22

you want to factor is it ? looks like a good idea !

Answer 23

\(\large 2^{p-1} - 1^{p-1} = (2-1)(2^{p-2 } + \cdots + 1)\)

Answer 24

hmm~

Answer 25

so there is a thm that states g is a prim root mod m then g^r is a prim rootmod m iff \(gcd(r, \phi{m})=1\)

Answer 26

could we extrapolate from there?

Answer 27

or since 2^p-1=1modp maybe we could use that?

Answer 28

leme pull up my NT notes :) don't seem to remember a thing lol

Answer 29

that's what I'm using... i had a polish teacher.

Answer 30

that class was awful

Answer 31

AH here so if we can prove that the only powers of 2 with a prim root are 2 and 4 we should be able to say the only possible ones for p squared are 4 and 16 so the only possible primes are 3 and 17

Answer 32

5 and 17 but i don't think that's right

Answer 33

5 would be 2^4=16/=1mod25
17 would be 2^16=65536/=1MOD289

Answer 34

nope ok so, we can prove that the only integers that can have prim roots are 2,4,p^r, and 2p^r st p is odd

Answer 35

Maybe this?

Answer 36

This first

Answer 37

maybe one of the exercises can lead us to something

Answer 38

isit burton book /.?

Answer 39

number 5 is espec. interesting

Answer 40

andrews

Answer 41

it's from dover publishing

Answer 42

its also chapter 7 to me >.<
same questions xD

Answer 43

lol

Answer 44

it's evilll isn't it?

Answer 45

yeah ,hehe

Answer 46

but #5 i think could be extremely useful here

Answer 47

brb

Answer 48

it intentionally leaves out p^2

Answer 49

but if we swing over to abstract algebra and thing about cyclic groups, we are essintially saying that this has no generators

Answer 50

hmmm