ad-bc=1ad-bc=1, w=au+bvw=au+bv and z=cu+dvz=cu+dv. Prove \gcd(u,v) = \gcd (w,z)\gcd(u,v) = \gcd (w,z).

As indicated indicated in the title,I am solving the following problem: If ad-bc=1, w=au+bv and z=cu+dv, prove \gcd(u,v) = \gcd (w,z) So from ad-bc=1 I was able to found out \gcd(a+b,c+d) = 1. From here I’m sort of lost as what to do with w = au + bv and z = cu + dv. … Read more

Since the gcd(a,b)=p(a,b) = p, where pp is prime, calculate the gcd\gcd(a^3,b) and the \gcd(a^2,b^3)\gcd(a^2,b^3)

My attempt p\mid a and p\mid b, then a = pq_1 , b = pq_2 \gcd(a^2,b) a^2 = (p^2 * q_1^2) ,\ b = p*q_2 To find the \gcd(a^2,b), I have to do the euclidean algorithm: (p^2q_1^2)\bmod (pq_2) From there I can’t Go on… Answer You know that p divides both a and b, but … Read more

Is the statement “(m,n)=d(m, n)=d if and only if there exist integers rr and ss such that rm+sn=dr m+s n=d” problematic?

My textbook Groups, Matrices, and Vector Spaces – A Group Theoretic Approach to Linear Algebra by James B. Carrell said that (m,n)=d if and only if there exist integers r and s such that rm+sn=d. We have 2⋅3+4⋅5=26, but (3,5)=1≠26. Could you please explain if this paragraph is problematic? Answer While true for d=26, the … Read more

Halving input but not at each step of a process

I am reading about an algorithm that takes as input 2 integers and does the following to calculate the GCD: If both are even then then shift right (=division by 2) both numbers and repeat If one is even then shift right (=division by 2) the even number only and repeat If both are odd … Read more

How to show that: $ \gcd \Big(2^{2^a}+1 , 2^{2^b}+1\Big)=1$

How to show that: $$ \gcd \Big(2^{2^a}+1 , 2^{2^b}+1 \Big)=1$$ Answer Assume WLOG that $b>a$. Note that $(2^{2^a}+1)|((2^{2^a})^{2^{b-a}}-1)=(2^{2^b}-1)$. (This follows from the fact that $x^2-1|x^{2^k}-1$ and $x+1|x^2-1$ for integer x and any positive integer k) Thus, it follows that $2^{2^b}-1=k(2^{2^a}+1)$. Now add two to both sides to get: $$2^{2^b}+1=k(2^{2^a}+1)+2$$ Thus, $\gcd(2^{2^a}+1,2^{2^b}+1)|2$. Since both numbers are … Read more

Proving that gcd\gcd\left(\frac a {\gcd(a,b)},\frac b {\gcd(a,b)}\right) =1

I need to show that the \gcd\left(\frac a {\gcd(a,b)},\frac b {\gcd(a,b)}\right) =1 I’m not sure exactly how to approach this .. I tried using the fact that \gcd(a,b)=d so d=ma+nb but I didn’t get too far Could anyone suggest where to start? Answer No need to break apart the abstraction: we can deduce this just … Read more

Given that pp is an odd prime, is the GCD of any two numbers of the form 2p+12^p + 1 always equal to 33?

I have checked it for some numbers and it appears to be true. Also I am able to reduce it and get the value 3 for specific primes p1, p2 by using the Euclidean algorithm but I am not able to find a general argument for all numbers. Answer Let p1,p2 be any two distinct … Read more

Prove that gcd(a,b)=gcd(b,a)\gcd(a,b) = \gcd(b,a)

I want to prove \gcd(a,b)=\gcd(b,a). I tried using the euclidean algorithm but that didn’t help me much. Answer If \gcd(a,b)=x then x \mid a and x\mid b this implies x \mid \gcd(b,a). By similar argument \gcd(b,a)\mid\gcd(a,b). i.e., \gcd(a,b) = \gcd(b,a). AttributionSource : Link , Question Author : Geoff , Answer Author : Michael Hardy