# Number TheoryDivisibility Problems

#### nano

##### New member
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
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

Staff member
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}$.

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

#### nano

##### New member
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

Staff member
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}$.

#### Ackbach

##### Indicium Physicus
Staff member
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
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

Staff member
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.

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
It wouldn't be k1a by any chance since it is the contradiction to your statement?

#### MarkFL

Staff member
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
It would be

k2a - k3a cannot equal k1a

#### MarkFL

Staff member
It would be

k2a - k3a cannot equal k1a
Okay, good!

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

$$\displaystyle k_1\equiv k_2-k_3$$ ?

#### nano

##### New member
So that it now looks like

k2 - k3 = k2 - k3 ?

#### MarkFL

Staff member
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
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

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