Using the Euclidian Algorithm, calculate gcd(260−1,280−1)
Formula: gcd(a,b)=gcd(b,a) gcd(a,b)=gcd(a−n∗b,b) gcd(a,a)=a
gcd(260−1, 280−1)=gcd(280−1, 260−1)280−1=1+2+22+23+…+279260−1=1+2+22+23+…+259220∗(260−1)=220+221+…+279(280−1)−220∗(260−1)=1+2+22+23+…+219(280−1)−220∗(260−1)=220−1=gcd((280−1)−220∗(260−1), 260−1)=gcd(220−1, 260−1)
gcd(220−1, 260−1)=gcd(260−1, 220−1)260−1=1+2+22+23+…+259220−1=1+2+22+23+…+219240∗(220−1)=240+241+…+259(260−1)−240∗(220−1)=1+2+22+23+…+239(260−1)−240∗(220−1)=240−1=gcd((260−1)−240∗(220−1), 220−1)=gcd(240−1, 220−1)
gcd(240−1, 220−1)240−1=1+2+22+23+…+239220−1=1+2+22+23+…+219220∗(220−1)=220+221+…+239(240−1)−220∗(220−1)=1+2+22+23+…+219(240−1)−220∗(220−1)=220−1=gcd((240−1)−220∗(220−1), 220−1)=gcd(220−1, 220−1)=220−1=1048575
gcd(260−1, 280−1)=gcd(260−1, 220−1)=gcd(240−1, 220−1)=gcd(220−1, 220−1)=220−1=1048575