Question

Suppose that \(p\) is a prime and \( p>3 \).Prove that each divisors of \(\large \frac{ 2^p+1}{ 3 }\) can be written in the form of \( 2pk + 1\) (\(k\) is a natural number).

Answer 1

for example if \(p=5\) then \(11 = 2(5) + 1\).

Answer 2

is it 2px + 1 , or 2pk + 1?

Answer 3

Oops !
*edited

Answer 4

We can try it by induction, hope induction is allowed ?

Answer 5

well nop, i don't think that is a good idea, because prime numbers are not continuosly distributed..sorry

Answer 6

2^p +1 = (3-1)^p -1 = -1 + C(p,1) 3 - C(p,2) 3^2 .... + 3^p +1
(-1)^p = -1 because p is odd (obviously)
=> 2^p +1 = C(p,1) 3 - C(p,2) 3^2 .... C(p,p) 3^p
(2^p +1)/3 = C(p,1) - C(p,2) 3 .... 3^(p-1)

Answer 7

hmm,why do u try hard ways ? :D

Answer 8

only prime divisors are of form 2pk+1 right ?

Answer 9

actually if prime divisors are of form 2pk+1, all other divisors also will be of form 2pk+1 i guess ?

Answer 10

yes ;)

Answer 11

then it is sufficient to prove it for prime divisors

Answer 12

right ;)

Answer 13

let q = C(p,1) - C(p,2) 3 .... 3^(p-1)
q = p j + 3^(p-1)
where j is some natural number.
Now we need to prove two things, 3^(p-1) -1 is always divisible by p.
and q is always even.
hmm

Answer 14

not, q , but q-1

Answer 15

let \(q \gt 3\) is a prime divisor of \(\frac{2^p+1}{3}\)

\(\large q | \frac{2^p+1}{3}\) and \(q \gt 3\) together imply that \(q | 2^p+1\)

yes ?

Answer 16

yes

Answer 17

thats almost same as what shubham arrived at..

Answer 18

so we have
\[2^p+1\equiv 0 \pmod{q}\]
which is same as
\[2^p\equiv -1 \pmod{q}\]

Answer 19

that means the order of \(2\) in modulo \(q\) is \(2p\)
By definition the order divides \(\phi(q)\) : \[2p|\phi(q)\\2p|q-1\\q = 2pk+1\]
for some integer \(k\)

Answer 20

nice ;) i just expected that proof ;)

Answer 21

you need to work \(q=3\) case separately as we have assumed \(q\gt 3\) above

Answer 22

but u only said the order of 2 in modulo q = 2p,i don't know how did u prove that but my proof is that if we suppose the order of 2 in mudulo q = r then we can say \(r|2p \)

Answer 23

we have 4 cases:
\(r=1\), \(r=p\) ,\(r=2\) , \(r=2p\)

Answer 24

we can say why r cannot be 1,p,2.so it's 2p.

Answer 25

for r=1 we have q|1,for r=2 we have q|3 so q|3 we can say why it cannot happen.and for r=p we have \(q|2^p - 1 \) and \(q|2^p +1 \) so \( q|2\)

Answer 26

that looks neat xD

Answer 27

if \(q=3\) then \( 2^{2p} \equiv 1 ~ (mod 9) \) , but the order of 2 mod 9 is 6,so \(6|2p\) then \(3|p\) but p cannot be 3.

Answer 28

\[2^p \equiv -1 \pmod{q}\]

another way to argue the order cannot be \(\le p\) is by noticing the "-1" on right hand side
if the order were 1 or p, then any power of it yields "1". But we have \(2^p \not \equiv 1 \pmod{q}\). This precicely allows us to conclude that the order of \(2\) cannot be \(\le p\)

Answer 29

and \( p>3 \) so the order is greater than 3! yes ,nice idea ;)

Answer 30

we're assuming \(q\gt 3\)