Question

find HCF

Answer 1

\(\Huge \tt \color{black}{(2^{100}-1,2^{120}-1)}\)

Answer 2

@ikram002p

Answer 3

hmmm idk any simply method , but both sides devide 3,11,31,41
thus gcf=3*11*31*41
hmm

Answer 4

@ganeshie8 have an idea ?

Answer 5

if \(\large a|b\), then \(\large 2^{a}-1 | 2^{b}-1\)

Answer 6

:O i dont remember this

Answer 7

u mean a divided by b??

Answer 8

yes "a|b" is read as "a divides b"

Answer 9

for example :

2 | 6

Answer 10

5 | 25

etc

Answer 11

but :O

Answer 12

u mean 2^20

Answer 13

\(\large a|b \implies b = aq\) for some \(q\)

so,

\(\large \begin{align}2^{b}-1 &= a^{aq}-1\\~\\&=(2^a)^q-1\\~\\&=(2^a-1)(\text{some stuff})\end{align} \)

Answer 14

@ikram002p thats the proof for \(\large a|b \implies 2^a-1 | 2^b-1\)

Answer 15

yeah :O
why i forget it :'(

Answer 16

but i still feel hmm something wrong about it

Answer 17

For this particular problem :

Notice that \(\large \gcd(100,120) = 20\)


\(\large 20|100 \implies 2^{20}-1 | 2^{100}-1\)

\(\large 20|120 \implies 2^{20}-1 | 2^{120}-1\)

Answer 18

so \(\large 2^{20}-1\) is a common factor of both the given numbers,
but how do we know it is the highest common factor ?

Answer 19

wrong about what ?

Answer 20

na nothing

Answer 21

we're using x^n-y^n formula

remember, x-y is a factor of x^n-y^n ?

Answer 22

(x^2-y^2)=(x+y)(x-y)

Answer 23

http://math.stackexchange.com/questions/117660/proving-xn-yn-x-yxn-1-xn-2-y-x-yn-2-yn-1

Answer 24

im ok with it now

Answer 25

Okay please explain it to mathmath333, i gtg for now..
also we're not done with this problem because we have just proven that 2^20-1 is a common factor, but we don't know whether it is the highest or not yet

Answer 26

i cant stay online , however
we might use
ax+by=d

Answer 27

devide
x=2^120-1
y=2^100-1
d=2^20-1
then show that
(x/d ,y/d) are relativly prime

Answer 28

eclids algorithm solve it right ?

Answer 29

what grade are you doing