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

Conjecture: gcd(rad(a+b),ab)=rad(gcd(a,b)) \gcd(\operatorname{rad}(a+b) ,ab)= \operatorname{rad}(\gcd(a,b))

I have discovered some exercise type conjectures which I can’t prove and this is one of them: Given positive integers a,b, then \gcd(\operatorname{rad}(a+b) ,ab)= \operatorname{rad}(\gcd(a,b)) Can this be proved or disproved? From time to time, when testing my growing math packages BigZ and Forthmath, I recognize some patterns which I can’t prove or disprove (or … 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

If gcd\gcd(a,b)=1 , then a-ba-b does not divide a+ba+b?

I think the following statement is true: Suppose a,b\in \mathbb{N}^+, such that \gcd(a,b)=1 and |a-b|\geq\mathbf3. Then a-b does not divide a+b. Can you help me to solve this problem? Answer If positive integer d divides both a+b, a-b d must divide a+b\pm(a-b) d must divide 2(a,b)=2 So, a+b,a-b can not have a common divisor >2 … Read more