Question

Prove that 2^n+1 is not divisible by 31

posting this for the third time

Answer 1

@ganeshie8

Answer 2

i am closing this as this is feedback section.
but ganeshie can continue his explanation here

Answer 3

lets move to math..

Answer 4

oh lets continue here... then :)

Answer 5

oh sorry my bad

Answer 6

you want me to move this there?

Answer 7

\(\large 2^n \equiv (2^5)^{\frac{n}{5}}\)

Answer 8

we oly need to consider the case n = 5k (we can get back to this later)

Answer 9

32 leaves a remainder 1 when divided by 31

Answer 10

\(\large 2^n \equiv (2^5)^{\frac{n}{5}} \equiv 1 \mod 31\)

Answer 11

that means, 2^n + 1 leaves a remainder 2 when divided by 31

Answer 12

QED

Answer 13

32 leaves a remainder 1 when divided by 31
isn't this equal to 32mod31=1

Answer 14

yess

Answer 15

how come 2^n=1mod31=1?

Answer 16

we're considering n = 5k case

Answer 17

2^n = (32)^k = (1)^k = 1 mod 31

Answer 18

other cases are : n=5k+1, 5k+2, 5k+3, 5k+4
they just leave a non-zero multiple of remainder of n=5k case

Answer 19

let me knw if congruences dont look familiar...
we can avoid the congruences and try to discuss in simple math...

Answer 20

yeah, can't we just avoid congruences?

Answer 21

we can avoid it completely if we are okay on one thing :

1) if \(a\) leaves a remainder of \(r\) when divided by \(b\), then :
\(a^n\) leaves a remainder of \(r^n\) when divided by \(b\)

Answer 22

that observation/fact is important for the proof. i dont see any way we can avoid using it...

Answer 23

is that always true?
for example
5/3 will give a remainder of 2
5^2/3 will give a remainder of 1
Am I wrong?

Answer 24

it is always true

Answer 25

let me adjust ur example a bit :
5/3 will give a remainder of 2
5^2/3 will give a remainder of 2^2

Answer 26

\(\large 2^2 \equiv 1 \mod 3\)

Answer 27

when we talk about remainders when divided by 3,
1 = 4 = 7 = 10 ...

Answer 28

okay now I got the whole thing.

Answer 29

Really appreciate you help. Thank you for everything

Answer 30

np :)