GCD Proving Assistance - Get Help Now!

[Joe20]

I have encountered difficulties in solving this question. Your help is greatly appreciated!

 

[Greg]

Hello Alexis87 and welcome to MHB! :D

We ask that our users show their progress (work thus far or thoughts on how to begin) when posting questions. This way our helpers can see where you are stuck or may be going astray and will be able to post the best help possible without potentially making a suggestion which you have already tried, which would waste your time and that of the helper.

Can you post what you have done so far?

 

[Joe20]

Thanks for the advise. I have no idea how to start.

 

[I like Serena]

We're talking about a proof by induction.
That means that the proof starts with a base case, which is followed by an induction hypothesis.
What could the base case be?

 

[Opalg]

I have encountered difficulties in solving this question. Your help is greatly appreciated!

View attachment 7690​

A few hints to get you started:

The neatest way to work with GCDs is to use the fact that the condition for $(a,b) = 1$ is that there exist integers $x,y$ such that $ax+by=1$.

Suppose that condition holds. Then (multiplying through by $by$) it follows that $axby + b^2y^2 = by = 1-ax.$ Therefore $$a(xby + x) + b^2y^2 = 1.$$ That equation is of the form $aX + b^2Y = 1$, which shows that $(a,b^2) = 1.$

Can you use that as the basis for an inductive proof that $(a,b^n) = 1$ for all $n$?

 

[Evgeny.Makarov]

That equation is of the form $aX + b^2Y = 1$, which shows that $(a,b^2) = 1.$

Can you use that as the basis for an inductive proof that $(a,b^n) = 1$ for all $n$?

I think the basis for an induction proof that $(a,b^n)=1$ for every positive integer $n$ is $(a,b)=1$ and not $(a,b^2)=1$.

 

[Opalg]

I think the basis for an induction proof that $(a,b^n)=1$ for every positive integer $n$ is $(a,b)=1$ and not $(a,b^2)=1$.

Yes, of course. But I was not implying that the base case should be $(a,b^2)=1$. What I was suggesting was a technique that might be used for proving the inductive step.