Welcome to our community

Be a part of something great, join today!

Number Theory Divisibility Problems

nano

New member
Nov 7, 2013
8
Hey, I've been stuck on these questions for awhile. They're bonus/ extra practice questions and I have a midterm coming up and I'm not quite comfortable with the process. If anyone can help me that'd be great!

Prove the following theorem: for all integers a, b and c, if a does not divide b - c
then a does not divide b or a does not divide c. Hint: an indirect proof would work
well.

Prove that there do not exist two positive integers x and y such that x^2 - 4y^2 = 14.
Additional information: you have all known for a long time that there are many
solutions to the equation x^2 + y^2 = z^2, where x, y and z are all positive integers.
This problem considers a slightly di erent, but similar looking, type of equations.
Hint: use an indirect proof, and start by factoring x^2 - 4y^2.


I don't fully understand how to write a proper proof. Thanks for anyone's help!
 

chisigma

Well-known member
Feb 13, 2012
1,704
Re: Extra practice help!

Hey, I've been stuck on these questions for awhile. They're bonus/ extra practice questions and I have a midterm coming up and I'm not quite comfortable with the process. If anyone can help me that'd be great!

Prove the following theorem: for all integers a, b and c, if a does not divide b - c
then a does not divide b or a does not divide c. Hint: an indirect proof would work
well.
Wellcome on MHB nano!...

The first theorem can be proved as follows... let's suppose that a|b and a|c with $b \ne c$, so that $b = \beta\ a$ and $c = \gamma\ a$. In such case is $b - c = (\beta - \gamma)\ a\ \implies a|(b-c)$ which constrasts the hypothesis, so that it must be false or a|b or a|c...

Kind regards

$\chi$ $\sigma$
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Re: Extra practice help!

For the first problem, I would first assume that $a$ does not divide $b-c$, hence:

\(\displaystyle a\ne k_1(b-c)\)

Then I would assume the complement of "$a$ does not divide $b$ or $a$ does not divide $c$" is true, i.e $a$ does divide $b$ AND $a$ does divide $c$ is true:

\(\displaystyle a=k_2b\)

\(\displaystyle a=k_3c\)

where $k_i\in\mathbb{N}$.

Can you show this leads to a contradiction?

For the second problem, I would factor as suggested, and consider the different integral factorizations of 14. What do you find?
 

nano

New member
Nov 7, 2013
8
Re: Extra practice help!

I don't quite understand what the k is supposed to mean in your proof. Am I supposed to pick some number b and c and multiply it by a different number k? Sorry, math easily confuses me
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Re: Extra practice help!

The parameters $k_i$ represent arbitrary natural numbers. If $a|b$ then we may write:

\(\displaystyle b=ka\)

I apologize, as I wrote things backwards in my post above, I should have written (as chisigma did):

For the first problem, I would first assume that $a$ does not divide $b-c$, hence:

\(\displaystyle b-c\ne k_1a\)

Then I would assume the complement of "$a$ does not divide $b$ or $a$ does not divide $c$" is true, i.e $a$ does divide $b$ AND $a$ does divide $c$ is true:

\(\displaystyle b=k_2a\)

\(\displaystyle c=k_3a\)

where $k_i\in\mathbb{N}$.

Can you show this leads to a contradiction?
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
Re: Extra practice help!

Incidentally, these questions are more number theory than discrete math. I will move your thread (and also retitle to be more specific).
 

nano

New member
Nov 7, 2013
8
I think I've figured out the second question I posted at least but the contradiction that I'm trying to find for the one you're helping me with still is stumping me. I apologize, if I'm being irritating since you've already restated the steps twice.
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
I think I've figured out the second question I posted at least but the contradiction that I'm trying to find for the one you're helping me with still is stumping me. I apologize, if I'm being irritating since you've already restated the steps twice.
You are not being irritating, especially given that I fouled up the first statement of the steps I gave. :D

In the statement:

\(\displaystyle b-c\ne k_1a\)

Substitute for $b$ and $c$ using the statements:

\(\displaystyle b=k_2a\)

\(\displaystyle c=k_3a\)

What do you get?
 

nano

New member
Nov 7, 2013
8
It wouldn't be k1a by any chance since it is the contradiction to your statement?
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
It wouldn't be k1a by any chance since it is the contradiction to your statement?
Let's take it one step at a time. What do you get when you make the substitutions I suggested?
 

nano

New member
Nov 7, 2013
8
It would be

k2a - k3a cannot equal k1a
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
It would be

k2a - k3a cannot equal k1a
Okay, good! :D

Now factor the left side. What happens if we define:

\(\displaystyle k_1\equiv k_2-k_3\) ?
 

nano

New member
Nov 7, 2013
8
So that it now looks like

k2 - k3 = k2 - k3 ?
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
So that it now looks like

k2 - k3 = k2 - k3 ?
No, it would be:

\(\displaystyle a\left(k_2-k_3 \right)\ne a\left(k_2-k_3 \right)\)
 

nano

New member
Nov 7, 2013
8
Oh forgot about including the a. Well, that looks like a contradiction right? Since both sides are identical yet it says it doesn't equal each other?
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Oh forgot about including the a. Well, that looks like a contradiction right? Since both sides are identical yet it says it doesn't equal each other?
Good, yes this is the contradiction for which we were looking. So we now know we must have:

$a$ does not divide $b$ or $a$ does not divide $c$

And this is what we were looking to prove.