Question

Show that the number of coprime positive integers less than \(2^n-1\) is divisible by \(n\) for all \(n\gt 1\)

Answer 1

@Marki

Answer 2

for example when n = 3 :
coprimes less than 2^3 -1 are {1,2,3,4,5,6} and 6 is divisible by 3 as desired

Answer 3

when n=4 :
coprimes less than 2^4-1 are {1,2,4,7,8,11,13,14} and 8 is divisible by 4

Answer 4

coprime is the number that have only 2 primes facors right ?
why prime is also coprime?

Answer 5

coprime is same as relatively prime

two integers are called coprime if the gcd is 1

Answer 6

gcd(15, 32) = 1 so 15 and 32 are coprime

Answer 7

ohh

Answer 8

i guess phi function gives the formula right ?

Answer 9

i see coprime to 2^n-1 not pairwise coprime i got it

Answer 10

yes another way to state the question is

prove \(\large n ~|~ \phi(2^n-1)\)

Answer 11

hmm remind me with some group theory

Answer 12

still remember the concept of `order` ?

Answer 13

Hint : order of 2 in modulo (2^n-1) is n

Answer 14

order means number of group , here we have phi(2^n-1)= order
hmm

Answer 15

i can see it clear if we took subgroups from coprime , but how to see it in number theory >.<

Answer 16

\[2^n-1 \equiv 0 \pmod{2^n-1}\implies 2^n \equiv 1 \pmod{2^n-1}\]

that means the order of \(2\) in modulo \(2^n-1\) is \(n\) because the minimum integer divisible by 2^n-1 is itself.

Answer 17

aha

Answer 18

and the order of any integer in module \(m\) divides \(\phi(m)\)
so we're done!

Answer 19

u directly used some theorem , which i cant remember >.<

Answer 20

from euler generalization we have

\[\large 2^{\phi(2^n-1)}\equiv 1 \pmod{2^n-1}\]

yes ?

Answer 21

yes

Answer 22

yes !!

Answer 23

and order of an \(2\) in module \(2^n-1\) is the smallest positive integer \(k\) that satisfies :
\[2^{k}\equiv 1 \pmod{2^n-1}\]

Answer 24

we have figured out earlier that the smallest integer satisfying that congruence is \(n\)

so k = order = n

Answer 25

fine so far ?

Answer 26

yes

Answer 27

** and order of \(2\) in module \(2^n-1\) is the smallest positive integer \(k\) that satisfies :
\[2^{k}\equiv 1 \pmod{2^n-1}\]

Answer 28

got it !!

Answer 29

eh i was so far from this >.<

Answer 30

we can show that that the order of any integer in modulo \(m\) divides \(\phi(m)\)

Answer 31

i was thinking like this
{a1,a2,a3,........,a_k} have phi(2^n-1) Order
and this is the same as
{a1, a_k+1}
{a2, a_k-1 }
.....
up to

subgroups of order 2 that have phi(2^n-1)/2 numbers of subgroups

and then got stuck :P

Answer 32

so u thinking of it like this
show that |Z_m| divides phi(m)

Answer 33

order of modulo m is m itself , right ?

Answer 34

show me ur argument

Answer 35

Definition of order :
order of integer \(a\) in modulo \(m\) is the smallest positive integer that satisfies below
\[a^{k} \equiv 1 \pmod m\]

Answer 36

from euler, we know that \(\phi(m)\) always satisfies above congruence
but \(\phi(m)\) need not be the "smallest" integer that satisfies, yes ?

Answer 37

ok so 1 as identity ?

Answer 38

ok im mixing btw two orders :P

Answer 39

consider powers of \(2\) in modulo \(7\) :

\(2^1\equiv 2 \\ 2^2\equiv 4\\\color{red}{2^3\equiv 1}\\2^4\equiv 2\\2^5\equiv 4\\\color{Red}{2^6\equiv 1}\)

Answer 40

well since its prime order always 7-1 :P

Answer 41

:O so order 3

Answer 42

order of 2 in modulo 7 is not 6
order is 3 here because 3 is the smallest power that yields 1

Answer 43

i remember that class 2 years ago >.<

Answer 44

yes yes yes yes yaaaaaaaaaaaaaay

Answer 45

this was something in ring >..<

Answer 46

and i remember a question in final exam it was
find all possible orders of 36 :D

Answer 47

something like this >.<

Answer 48

in not off

Answer 49

\(\phi(36) = 12\)

since we know that the order divides \(\phi(36)\), we only need to check the divisors of \(12\)

Answer 50

yes yes exactly :P

Answer 51

so the possible orders in modulo 36 are {2, 3, 4, 6, 12 }

Answer 52

include 0

Answer 53

definition takes care of that
by definition order is the smallest "positive" integer

Answer 54

yes i know what definition is :P 0 is just memeber of ideal
we set it when there is no other integer ( just a base )

Answer 55

and we used to map it like this