Question

two number theory problems,just give the idea to solve it...

Answer 1

1) Find all values for n in which \(7 | 2^n - 1\)
2)Prove that there's no natural number such as n in which \(7 | 2^n + 1\)

Answer 2

if we suppose n=3k,then it would be

Answer 3

but is there any answers besides this?

Answer 4

\[2^n \equiv 1 \pmod 7\]
the order of 2 in modulo 7 is 3
so \(n \equiv 0 \pmod 3\)

Answer 5

there cannot be any other answers because
\[a^m \equiv1 \pmod {n} \implies \mathrm{ord}(a) | m\]

Answer 6

what do you mean? i havn't seen that symbol ( ord(a) ),how about this one:

n=3k + 1 --> \(2^{3k} \equiv 1 (\mod ~ 7) ~ so ~ 2(2^{3k}) \equiv 2 ~ (\mod ~ 7)\)
n=3k+2 --> \(2^{3k} \equiv 1 (\mod ~ 7) ~ so ~ 2^2(2^{3k}) \equiv 4 ~ (\mod ~ 7)\)

Answer 7

that works but again calling DA for proving this is bit distracting
these problems are part of euler generalization and primitive roots right ?

Answer 8

DA : Division Algorithm

Answer 9

wait sumbody xplain what is 7|2^n

Answer 10

a | b

is read as

a divides b

Answer 11

oh.makes sense........I can now solve it

Answer 12

for example :

3 | 15

4 | 20

Answer 13

for that U have to take MATHEMATICAL INDUCTION

Answer 14

U HAVE TO PROVE FOR 2^n+1 and then come back to 2^n

Answer 15

@PFEH.1999 take a quick look at this for order
http://en.wikipedia.org/wiki/Multiplicative_order

maybe lets stick to DA if primitive roots are not covered yet

Answer 16

for the second part

Answer 17

well i havn't study that so far,thank you ;) and for second part?

Answer 18

@cambrige , induction? i don't think it does work...

Answer 19

DA will work
use the same trick, test n = 3k, 3k+1, 3k+2 and show that remainders are nonzero

Answer 20

thank you,got it ;)

Answer 21

what @ganeshie8 showed is induction

Answer 22

np :) DA is pretty neat and always works. its kind of induction yes :)