Making Sure

File: proof2.jpg (2MB, 2500x3333px) Image search: [Google]

2MB, 2500x3333px

here is the second page of the proof

> using more then 5 words in a proof
NIBBA WHAT

>from theorem 1.4 we know that if x|yz then x|y or x|z
This is false. Let x = 6, y = 2, z = 3. I don't know what theorem 1.4 says, but it probably doesn't say what you think it says.

>>9137556
pls no bully

>>9137558
my bad, theorem 1.4 is as follows:

if a|bc and (a,b)=1 then a|c

>>9137582
>my bad, theorem 1.4 is as follows:
Well, then you're back at step 1.

>>9137592
I am using that theorem to basically say that due to that theorem d either divides b or b^k which and we assume the other piece (b^k and b respectively) share 1 as their gcd with d. This means d=1 due to that u feel me

>>9137602
Yeah, but the ACTUAL theorem 1.4 of >>9137582 doesn't help you one bit in proving that.

>>9137624
can you explain, I feel that by using proof by cases does use theorem 1.4

>>9137533
I think you're going down the wrong path.

You have a|b (b^k)
By induction hypothesis, (a,b^k) = 1
By the original assumption, (a,b) = 1
Therefore a doesn't divide (b^k+1). Clearly, if m doesn't divide n, they're coprime so you're done.

>>9137761
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

>>9137799
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.

>>9137853
well you would have to have another asumption stating that a<=b^c for all c in the naturals. What if a>b^c my dude

>>9138002
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.

>>9138070
I think you are confused about my nomenclature though. Why are you assuming a|b^k in this >>9137761 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

>>9138353
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.

>>9138353
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.

>>9138476
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

>>9137533
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.

>>9137556
>using more than 3 letters in a proof

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

>>9138548
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

>>9138434
>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.
>>9137761
>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 >>9138548
, 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 >>9137761
>>9138434
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.

>>9138587
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.

>>9138587
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.

>>9138587
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.

>>9138635
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.

>>9138551
>using more than 1 dimension in a proof

>>9138737
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.

>>9138635
>>9138624
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 ;)

>>9138810
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.

>>9138826
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

>>9138869
>(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

>>9138745
>using

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

>>9138869
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)

>>9138886
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<a and a=pn
p(n+1) is not coprime with a, yet gcd (a, pn+p) is not a otherwise we would have a|p
I think you need to brush up on implications & equivalences

>this whole braincel thread

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

>>9138910
what do you think exactly this is a counterexample to?

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

>>9138922
>(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"

>>9138952
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.

>>9137533
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)(a,b) = 1
and we're done.

The only result you need is
(a,bc)<=(a,b)(a,c).

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

>>9139081
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.

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

>>9139145
yeah I was guessing you meant that but I was just 'aving a go.
>>9139361
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

>>9139459
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

>>9139482
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.

>>9139670
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

>>9137533
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.

>>9140682
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