Making Sure

Interesting, I see what you are saying there but I am pretty set on using the theorem I provided (to reiterate if a|bc and (a,b)=1 then a|c) because in this problem I am allowed to use prime factorization but I want to be able to prove it with that theorem. Specifically because my professor said it was possible and I want to satiate my ego

Then it has to be a proof by contradiction because I already proved a didn't divide
b (b^k) which is what we were looking for.

So, assume a does divide b (b^k).
Since (a,b) = 1 by our original assumption, that means by theorem 1.4 that a|b^k. This a contradiction to the induction hypothesis that (a,b^k) = 1. Therefore, a doesn't divide b (b^k). So (a,b^k+1) = 1. Qed.

Seems needlessly convoluted when my direct proof works.

well you would have to have another asumption stating that ab^c my dude

You're right. You can do it by cases then. The case that a>bc is automatically a contradiction. I should have included it. Cheers.

I think you are confused about my nomenclature though. Why are you assuming a|b^k in this when I set d=(a,b^k(b)) which by definition of GCD d|a and d|b^(k+1). Just because 2 integers have a GCD of 1 does not necessarily mean that one integer divides the other and vice versa

Because, (a,b^k) = 1 is equivalent to saYing a does not divide b^k.

Introducing a new term d will only take you further away from the results.

Just to put the kabosh on this,

I'll ask: why use d? You can apply your theorem without the introduction of any extra terms. And the theorem you want to use is already extraneous to the solution.

If you want to apply the theorem, you need two properties of d:
d|b (b^k) and (d,b) = 1. Then you can say by 1.4 that d|b^k. This says nothing about a and you need the relation between a and b to finish the proof.

I use d because if I state that d=gcd (a,b^(k+1)) then we know that by definition of gcd that d|a and d|b^(k+1)

I am then able to use theorem 1.4 with the 2 cases where:
d|b and (d, b^k)=1
-and-
d|b^k and (d,b)=1

Now I do agree that there are better ways to do this but I'm just a hard ass

couldn't you simply state that
there is a single way to write a and b as a product of primes (to a certain power) with no primes in common
as b^n can be written as the product of those same primes to said powers x n, then that is the only way to write b^n as a product of prime
it still has no common prime factor with a?
induction seems like a lot of autism for nothing.
I don't know at which stage of your studies you are, but that's a result you should be familiar with if you're in high school.

>using more than 3 letters in a proof

Yea but I specifically want to use induction and not use prime factorization as I stated in the OP

also i have crippling autism which is why I am posting on budget lead painted chinese bootletg fidget spinner forums about autistic ways to solve math

>Because, (a,b^k) = 1 is equivalent to saYing a does not divide b^k.
no it is not. 6 does not divide 8, yet they aren't coprime.
>Clearly, if m doesn't divide n, they're coprime so you're done.
no, see above.
I think what you meant is
assume c is a prime that divides both a and b^(k+1)=b*b^k, then it divides both a AND (b OR b^k) which is not possible by hypothesis.
that's roughly equivalent to , but all proofs would be "roughly equivalent" to each other given how elementary the question is.
Also, by the way, I might have misunderstood but
>"Theorem 1.4" if x|yz for some x,y,z in Z and x>0 then x|y and/or x|z
is just plain wrong.
x=6, y=3, z=4
just out of curiosity, are you in high school (nothing derogative here). Same for you guys made some basic mistakes, forunately there are few things you need to know to excel at entry level number theory, you should brush up on that.

I am OP and I am not in high school, just stupid rusty at proofs and taking both the pre-req class and this class at the same time so it is a little rough sometimes. You also misread theorem 1.4 and I miswrote it in my proof.

Theorem 1.4: if x|yz for some x,y,z in Z and x>0 and (x,y)=1 then x|z. This being said, if (x, z)=1 then x|y

Not to be a dick but that theorem is correct. But I do want to stress that I really appreciate you reading through the proof and the thread fairly carefully, I was getting a little frustrated because I felt few people in this thread read the proof near as thorough as you did.

You're right in general, but we assumed that gcd (a,b) = 1 therfore, they are in fact coprime.

Your counter example doesn't work because gcd (6,3) = 3 and gcd (6,4) = 2 but the theorem says gcd (a,b) = 1.

You're the one making the mistakes.

Since I think you missed the point of my argument, I'll be more specific:
Let a = 6
b = 2
k = 3
Then gcd (6,2^3) = 2
We said that gcd (a,b^k) = 1 by the induction hypothesis.

You can't give a counter argument that doesn't fulfill the requirements of the problem. The counter example had to meet all criteria and still lead to a false statement.

yes but then (a,b)=2 which doesnt follow our initial hypothesis my dude.

Also, I just spoke with my professor and she said my logic is fine up until my conclusion. I made my conclusion too convoluted, probably because I was drinking while doing this, but the main point is my logic is sound. The conclusion should be something along the lines of

Since we have proved that d|a and d|b(b^k) we have shown that (a, b^(k+1))=d=1 thus proving the hypothesis that if gcd(a, b) = 1 then (a, b^n)=1 for all n>=1 by the principle of mathematical induction.

>using more than 1 dimension in a proof

I'm agreeing with you. You meant to reply to the other guy. My orginal proof at the start of the thread is what you said. I just think using d and using the theorem is pointless because d has to be 1 from our assumptions.

no I got your point, I was just pointing out that the statements, on their own, were false
Also you used "a" where you should've been using "d" using OP's notation which I got later.
And
>(a,b^k) = 1 is equivalent to saYing a does not divide b^k.
is valid only if we assume a is prime which it isn't. even if you meant d you can't assume it's prime because it's stated nowhere as it's the gcd of a and b^(k+1). Of course OP could've (and probably should've) used the smallest prime cd but he didn't.
What I'm trying to say is you should define the numbers you're using and write down the hypothesis you're using.
The counterexamples met all the criteria in your post, which is none in particular.
And you should stop taking things personally, as they say there's no "I" in math ;)

No, I intentionally omitted d because it's not necessary.

And my claim is correct.
We know that (a,b) = 1
We know that (a,b^k) = 1

Now, find a,b such that a doesnt divide b and a,b are not coprime. I'll wait.

I don't know what you're on about but
>(a,b^k) = 1 is equivalent to saying a does not divide b^k

>a does not divide b^k => (a,b^k)=1 when a is not 1
(which we can assume is not the case)

>a is prime
there's no way around it.
what you're saying is
>(a does not divide b^k AND (a,b^k) = 1) => (a,b^k) = 1
Which of course is true but that tells us nothing about the truth of
>(a,b^k) = 1 is equivalent to saying a does not divide b^k
which again is true if and only if a is a prime

>(a,b^k) = 1 is equivalent to saying a does not divide b^k

>a does not divide b^k => (a,b^k)=1
(when a is not 1 which we can assume is not the case)
is what I meant my bad

>using

>You also misread theorem 1.4 and I miswrote it in my proof
Well which one is it? That's rich.

Let a = 4. Let b = 9.
4 does not divide 9
(4,9) = 1
4 is not prime. Your argument is invalid.
Don't put words in my mouth, find a concrete example where what I said was wrong. (Thereally isn't one)

you misunderstood.
whenever
>"a doesn't divide b" IMPLIES "a and b are coprime"
then
>a is prime
because to put it simply, that means that a has no other divisors than itself that it could have in common with b.
basically it's equivalent to
>if a is not coprime with some b then gcd(a,b)=a
try imagining a scenario where a isn't prime.
then it has a prime divisor p

>this whole braincel thread

I'm not misunderstanding. My counter example holds. You just keep reating something that's not true.

what do you think exactly this is a counterexample to?

To the claim that (a,b) = 1 implies a does not divide b iff a is prime.

>(a,b) = 1 implies a does not divide b iff a is prime
I did not say that
I said that
>""(a,b) = 1" iff "a does not divide b"" iff "a is prime"

Then there's nothing to talk about because I originally said
(a,b) = 1 implies a does not divide b.
I never said it works both ways. And I never used it the other way either.

Obviously a does not divide b does not imply (a,b) = 1. And I never used that in my original argument, so I don't know why you're arguing about it when it's not relevant.

Not going to read all that, but a two pages long "proof" will not be accepted by your professor. The most important thing you could learn in a math course is that a trivial result requires a trivial proof. Here is a one-liner satisfying your requirements:

Assume (a,b) = 1 and (a,b^k)=1, then
(a,b^(k+1))

>(a,b^k) = 1 is equivalent to saYing a does not divide b^k
Means exactly that it goes both ways

I'm sorry. I was using equivalent in the linguistic sense, not as a logical statement. What I really meant was that logically, the forward direction is true. I also think the statement is obvious enough that it doesn't need to be proven.

My bad man, I was posting in between courses and wasn't paying enough attention to what I was posting.

yeah I was guessing you meant that but I was just 'aving a go.
no worries. as stated multiple times during the thread though, the proof could be much shorter even if you're hell bent on using induction

yea it could be a better proof but im autistic. Turns out my prof was wrong in saying to stay away from benoutz identity and I am a little salty about it. Gonna write down a proof with benou and prove her wrong because that is how I originally wanted to do the prof. I think my biggest problem is I like to drink and do proofs

So, gcd at its core is about prime factorization. You can't avoid it in this proof. You can do it with the diophantine equation instead.

Yes GCD is, at its core, about prime factorization but I did not want to use this fact in the proof. Also, I did not want to use the diophantine equation either because I wanted to be difficult

This is the most verbose proof I've seen for what should really be fairly succinct. No offense, but I remember when one of my profs told me he felt like he was running a marathon reading a proof of mine which was like that and encouraged me to be more succinct.

Well put, I am just getting back into proof writing and am using more words than necessary to make sure my logic makes sense and it is partial paranoia about the professor not understanding what I do. I didn't take any offense tho and am trying to find that balance of what makes a well explained and thorough proof to what makes a fucking book