Some number theory proofs

In summary, if a and b are relatively prime, then their prime factorizations don't have any prime factors in common. This implies that each a_i^{\alpha_i} and each b_i^{\beta_i} divides c. So c is divided by each a_i^{\alpha_i} and each b_i^{\beta_i}. Hope that makes sense.
  • #1

STEMucator

Homework Helper
2,076
140

Homework Statement


I've got two questions out of my textbook. I'll list both of them and my attempts below.

(1) Suppose : [itex]a, b, c\in Z, a|c \space \wedge \space b|c.\space[/itex]If a and b are relatively prime, show ab|c. Show by example that if a and b are not relatively prime then ab does not divide c ( Didn't know how to do does not divide in latex ).

(2) Show that 5n+3 and 7n+4 are relatively prime for all n ( I'm assuming the book means [itex]\forall n\in N[/itex]).


Homework Equations



Supposing that p is a prime, then p has a unique prime factorization :

[itex]p = p_{1}^{α_1} ... p_{n}^{α_n}[/itex]

Also I believe that (1) is Euclid's Lemma backwards...

I think that gcd(a,b) = as + bt for some integers s and t will be useful for (2) not positive yet though.

The Attempt at a Solution



(1) We have by hypothesis that a and b are relatively prime integers That is, they are composed of unique prime factorizations. Let :

[itex]a = a_{1}^{α_1} ... a_{n}^{α_n}[/itex]

[itex]b = b_{1}^{β_1} ... b_{n}^{β_n}[/itex]

be prime factorizations for a and b.

If a|c, we know that there is some integer s such that c = as and if b|c, we know that there is some integer t such that c = bt.

Am I going in the right direction here? I'll save (2) for after (1) is figured out.
 
Physics news on Phys.org
  • #2
So far so good. Think about the prime factorization of [itex]c[/itex]. By the way, to be properly general, you shouldn't use [itex]n[/itex] for the number of distinct prime factors of both [itex]a[/itex] and [itex]b[/itex].
 
  • #3
jbunniii said:
So far so good. Think about the prime factorization of [itex]c[/itex]. By the way, to be properly general, you shouldn't use [itex]n[/itex] for the number of distinct prime factors of both [itex]a[/itex] and [itex]b[/itex].

Heya jbun, duly noted about n, I'll try not to be so sloppy.

Anyway, I digress.

c is not necessarily prime though? Why would I require its factorization.
 
  • #4
Zondrina said:
c is not necessarily prime though? Why would I require its factorization.
Because you want to show that ab divides c, and you have prime factorizations for a and b.

By the way, I'm not sure I understand your question. A prime number has a trivial prime factorization, consisting of itself. Prime factorizations are more interesting for numbers that are NOT prime.
 
  • #5
jbunniii said:
Because you want to show that ab divides c, and you have prime factorizations for a and b.

By the way, I'm not sure I understand your question. A prime number has a trivial prime factorization, consisting of itself. Prime factorizations are more interesting for numbers that are NOT prime.

Ahh I had a derp for a moment there. My bad.

So let's see if I can continue this now. So I should take either one of the cases a|c or b|c and prove that if either a or b is relatively prime, then ab|c ( Because of symmetry of course )?
 
  • #6
Zondrina said:
So let's see if I can continue this now. So I should take either one of the cases a|c or b|c and prove that if either a or b is relatively prime, then ab|c ( Because of symmetry of course )?

"If either a or b is relatively prime" doesn't make any sense. An individual number can't be relatively prime. PAIRS of numbers can be relatively prime. If a and b are relatively prime, that means their prime factorizations don't have any prime factors in common. So think about what that implies about the prime factorization of c.
 
  • #7
jbunniii said:
"If either a or b is relatively prime" doesn't make any sense. An individual number can't be relatively prime. PAIRS of numbers can be relatively prime. If a and b are relatively prime, that means their prime factorizations don't have any prime factors in common. So think about what that implies about the prime factorization of c.

So then I would have ( excuse the n for now ) :

[itex]a|c \Rightarrow a_{1}^{α_1} ... a_{n}^{α_n}|c[/itex]

and obviously

[itex]b|c \Rightarrow b_{1}^{β_1} ... b_{n}^{β_n}|c[/itex]

Excuse my noobish thought process here, but I'm not quite sure what these tell me about the prime factorization of c? Would these imply that some aiαi and some bjβj divide c?
 
  • #8
Zondrina said:
Excuse my noobish thought process here, but I'm not quite sure what these tell me about the prime factorization of c? Would these imply that some aiαi and some bjβj divide c?
In fact, it's easy to see that they all divide c.

Hopefully have encountered the following elementary theorem: if [itex]m[/itex] divides [itex]n[/itex] and [itex]n[/itex] divides [itex]p[/itex], then [itex]m[/itex] divides [itex]p[/itex]. This is true for any integers, not just prime numbers.

So take one of the factors of [itex]a[/itex]: [itex]a_i^{\alpha_i}[/itex] divides [itex]a[/itex], and [itex]a[/itex] divides [itex]c[/itex], therefore by the elementary theorem above, [itex]a_i^{\alpha_i}[/itex] divides [itex]c[/itex]. Same argument holds for the factors of [itex]b[/itex].

So far, we haven't used the fact that the [itex]a_i[/itex]'s and [itex]b_i[/itex]'s are prime. You will need to take advantage of that in order to finish the theorem.
 
  • #9
jbunniii said:
In fact, it's easy to see that they all divide c.

Hopefully have encountered the following elementary theorem: if [itex]m[/itex] divides [itex]n[/itex] and [itex]n[/itex] divides [itex]p[/itex], then [itex]m[/itex] divides [itex]p[/itex]. This is true for any integers, not just prime numbers.

So take one of the factors of [itex]a[/itex]: [itex]a_i^{\alpha_i}[/itex] divides [itex]a[/itex], and [itex]a[/itex] divides [itex]c[/itex], therefore by the elementary theorem above, [itex]a_i^{\alpha_i}[/itex] divides [itex]c[/itex]. Same argument holds for the factors of [itex]b[/itex].

So far, we haven't used the fact that the [itex]a_i[/itex]'s and [itex]b_i[/itex]'s are prime. You will need to take advantage of that in order to finish the theorem.

Surprisingly this theorem is not directly in my textbook, but I know that it is true ( I've seen the proof before ). I'll take a moment to put everything together nicely in one post here...

We have by hypothesis that a and b are relatively prime integers That is, they are composed of unique prime factorizations. Let :

[itex]a = a_{1}^{α_1} ... a_{t}^{α_t}[/itex]

[itex]b = b_{1}^{β_1} ... b_{s}^{β_s}[/itex]

be prime factorizations for a and b. So we know that some [itex]a_{i}^{α_i}, 1≤i≤t[/itex] divides a. Since [itex]a_{i}^{α_i}|a[/itex] and [itex]a|c[/itex], we know [itex]a_{i}^{α_i}|c.[/itex]

Similarily, we know that some [itex]b_{i}^{β_i}, 1≤i≤s[/itex] divides b. Since [itex]b_{i}^{β_i}|b[/itex] and [itex]b|c[/itex], we know [itex]b_{i}^{β_i}|c.[/itex]

If a|c, we know that there is some integer q such that c = aq and if b|c, we know that there is some integer p such that c = bp.

Hmm as per your comment about the ai's and bi's. Since they are prime... hmm I'm trying to formulate the point you're trying to get across. Does it have something to do with the gcd of them? ( This is my first time writing a proof like this one so sorry if I seem a bit lost ).
 
Last edited:
  • #10
Zondrina said:
Surprisingly this theorem is not directly in my textbook, but I know that it is true ( I've seen the proof before ). I'll take a moment to put everything together nicely in one post here...

We have by hypothesis that a and b are relatively prime integers That is, they are composed of unique prime factorizations.
Well, all integers have unique prime factorizations. You don't need the fact that a and b are relatively prime in order for that to be true. So "that is" is the wrong wording here.

[itex]a = a_{1}^{α_1} ... a_{t}^{α_t}[/itex]

[itex]b = b_{1}^{β_1} ... b_{s}^{β_s}[/itex]

be prime factorizations for a and b. So we know that some [itex]a_{i}^{α_i}, 1≤i≤t[/itex] divides a. Since [itex]a_{i}^{α_i}|a[/itex] and [itex]a|c[/itex], we know [itex]a_{i}^{α_i}|c.[/itex]
Actually, this is true for all of the [itex]a_{i}^{\alpha_i}[/itex], not just some.

Similarily, we know that some [itex]b_{i}^{β_i}, 1≤i≤s[/itex] divides b. Since [itex]b_{i}^{β_i}|b[/itex] and [itex]b|c[/itex], we know [itex]b_{i}^{β_i}|c.[/itex]
Same comment here.

Hmm as per your comment about the ai's and bi's. Since they are prime... hmm I'm trying to formulate the point you're trying to get across. Does it have something to do with the gcd of them? ( This is my first time writing a proof like this one so sorry if I seem a bit lost ).
Well, you need the fact that if p and q are distinct prime numbers, and p and q both divide c, then pq divides c. Then you build up from there.

However, this is a pretty grungy proof. There is a much slicker one involving the fact that you mentioned in your original post. As you said, if a and b are relatively prime, that means their gcd is 1, which in turn means that we can find integers x and y such that ax + by = 1.

Now, big hint: try multiplying both sides of that equation by c, and see what you can conclude.
 
  • #11
jbunniii said:
Well, all integers have unique prime factorizations. You don't need the fact that a and b are relatively prime in order for that to be true. So "that is" is the wrong wording here.Actually, this is true for all of the [itex]a_{i}^{\alpha_i}[/itex], not just some.Same comment here.Well, you need the fact that if p and q are distinct prime numbers, and p and q both divide c, then pq divides c. Then you build up from there.

However, this is a pretty grungy proof. There is a much slicker one involving the fact that you mentioned in your original post. As you said, if a and b are relatively prime, that means their gcd is 1, which in turn means that we can find integers x and y such that ax + by = 1.

Now, big hint: try multiplying both sides of that equation by c, and see what you can conclude.

I did notice something about the gcd indeed... Tossing out everything else and using this slick trick :

"If a and b are relatively prime, that means their gcd is 1, which in turn means that we can find integers x and y such that ax + by = 1"

Would I need what I said earlier? :

"If a|c, we know that there is some integer s such that c = as and if b|c, we know that there is some integer t such that c = bt."

So : gcd(a,b) = 1 = ax + by ( For some integers x and y ).

ax + by = 1
c(ax+by) = c

... What can I conclude? c|c, but that's obvious.
 
  • #12
Zondrina said:
"If a|c, we know that there is some integer s such that c = as and if b|c, we know that there is some integer t such that c = bt."

So : gcd(a,b) = 1 = ax + by ( For some integers x and y ).

ax + by = 1
c(ax+by) = c

... What can I conclude? c|c, but that's obvious.
Well, you just said that c = as and c = bt. Try making those substitutions in c(ax+by) = c.
 
  • #13
Wait wait waaaaait something just hit me. Let me re-write this nice and clean.

If a and b are relatively prime, we know that gcd(a,b) = 1 = ax + by for some integers x and y.

If a|c, we know that there is some integer q such that c = aq. If b|c, we know that there is some integer t such that c = bt.

Now, since a|c, then a|bt. Since b|c, then b|aq.

Now consider :

ax + by = 1
acx + bcy = c

Since we know that a|bt, we know that a|acx. We also know that because b|aq, b|bcy as well.

Is this what you were getting at?
 
  • #14
Zondrina said:
Wait wait waaaaait something just hit me. Let me re-write this nice and clean.

If a and b are relatively prime, we know that gcd(a,b) = 1 = ax + by for some integers x and y.

If a|c, we know that there is some integer q such that c = aq. If b|c, we know that there is some integer t such that c = bt.

Now, since a|c, then a|bt. Since b|c, then b|aq.

Now consider :

ax + by = 1
acx + bcy = c

Since we know that a|bt, we know that a|acx. We also know that because b|aq, b|bcy as well.

Is this what you were getting at?

Not exactly. I'm not sure why you needed any manipulation to conclude that a|acx and b|bcy. This is obvious because acx = a(cx) and bcy = b(cy).

You have established that this is true:

acx + bcy = c

The goal is to conclude that ab|c. You can do this by showing that ab|acx and ab|bcy, because then ab divides both terms on the left hand side. This means that ab divides the left hand side. Therefore it also divides the right hand side.

So, all you need to do is show that ab|acx, and ab|bcy.
 
  • #15
jbunniii said:
Not exactly. I'm not sure why you needed any manipulation to conclude that a|acx and b|bcy. This is obvious because acx = a(cx) and bcy = b(cy).

You have established that this is true:

acx + bcy = c

The goal is to conclude that ab|c. You can do this by showing that ab|acx and ab|bcy, because then ab divides both terms on the left hand side. This means that ab divides the left hand side. Therefore it also divides the right hand side.

So, all you need to do is show that ab|acx, and ab|bcy.

EDIT : I'll attempt this in the morning... my brain has been off for hours now and I'm basically struggling to see obvious things. I'll post when I'm fresh.
 
Last edited:
  • #16
Okay! So after some rest and a little bit of time looking at this I think I've got it.

Since a|c and b|c, there exist integers x and y such that ax = by = c. Also, since gcd(a,b)=1, we know there exist integers s and t such that 1 = as + bt.

Now consider :

1 = as + bt
c = asc + btc
c = as(by) + bt(ax)
c = (ab)sy + (ab)tx
c = ab(sy + tx)

Hence we see that ab|c as desired.

As for an example, take a = 4, b = 6 and c = 36. So gcd(a,b) = 2 which means a and b are not relatively prime.

Notice that 4|36 and 6|36, however ab=24[itex]\nmid[/itex]36 as desired.
 
Last edited:
  • #17
Zondrina said:
Okay! So after some rest and a little bit of time looking at this I think I've got it.

Since a|c and b|c, there exist integers x and y such that ax = by = c. Also, since gcd(a,b)=1, we know there exist integers s and t such that 1 = as + bt.

Now consider :

1 = as + bt
c = asc + btc
c = as(by) + bt(ax)
c = (ab)sy + (ab)tx
c = ab(sy + tx)

Hence we see that ab|c as desired.

As for an example, take a = 4, b = 6 and c = 36. So gcd(a,b) = 2 which means a and b are not relatively prime.

Notice that 4|36 and 6|36, however ab=24[itex]\nmid[/itex]36 as desired.

Perfect!
 
  • #18
jbunniii said:
Perfect!

Phew! Sleep does wonders for me haha.

I'll attempt the second question after my class, but I am pretty sure I know how to do it. I'll post my attempt later.
 
  • #19
Okay now for #2 : Show that 5n+3 and 7n+4 are relatively prime for all integers n.

This is equivalent to showing that gcd(5n+3, 7n+4) = 1 for all integers n. We know that the gcd is a linear combination of a and b, so it suffices to show that there exists a linear combination of 5n+3 and 7n+4 that gives 1.

So, let : gcd(5n+3, 7n+4) = d = s(5n+3) + t(7n+4) for some integers s and t.

Clearly by some very easy inspection, take s = 7 and t = -5. Then we observe that :

7(5n+3) - 5(7n+4) = 35n + 21 - 35n - 20 = 1 = d.

Since d|5n+3 and d|7n+4 we know d|1 ( Clearly the only positive divisor of 1 is 1 ). Therefore we conclude that d = 1 = gcd(5n+3,7n+4).

Is this good?
 
  • #20
Zondrina said:
Okay now for #2 : Show that 5n+3 and 7n+4 are relatively prime for all integers n.

This is equivalent to showing that gcd(5n+3, 7n+4) = 1 for all integers n. We know that the gcd is a linear combination of a and b, so it suffices to show that there exists a linear combination of 5n+3 and 7n+4 that gives 1.

So, let : gcd(5n+3, 7n+4) = d = s(5n+3) + t(7n+4) for some integers s and t.

Clearly by some very easy inspection, take s = 7 and t = -5. Then we observe that :

7(5n+3) - 5(7n+4) = 35n + 21 - 35n - 20 = 1 = d.

Since d|5n+3 and d|7n+4 we know d|1 ( Clearly the only positive divisor of 1 is 1 ). Therefore we conclude that d = 1 = gcd(5n+3,7n+4).

Is this good?
Yes, that works! Suppose your very easy inspection hadn't worked - do you know another way to solve the problem?
 
  • #21
jbunniii said:
Yes, that works! Suppose your very easy inspection hadn't worked - do you know another way to solve the problem?

Hmm... perhaps strong induction? I'm not really sure how I would've come to a conclusion here otherwise.
 
  • #22
Zondrina said:
Hmm... perhaps strong induction? I'm not really sure how I would've come to a conclusion here otherwise.

Do you know the Euclidean algorithm for calculating the gcd?
 
  • #23
jbunniii said:
Do you know the Euclidean algorithm for calculating the gcd?

Hmm I believe that I would continue subtracting the larger number from the smaller one over and over again until both numbers are the same, then that number I get at the end is the gcd of both my original numbers. I see now that if I had done that with 5n+3 and 7n+4 with 7n+4 being the bigger number first I would see that their gcd = 1.
 
  • #24
Zondrina said:
Hmm I believe that I would continue subtracting the larger number from the smaller one over and over again until both numbers are the same, then that number I get at the end is the gcd of both my original numbers. I see now that if I had done that with 5n+3 and 7n+4 with 7n+4 being the bigger number first I would see that their gcd = 1.
Sounds right, you can always use this method if you can't find the gcd some other slicker way.
 
  • #25
jbunniii said:
Sounds right, you can always use this method if you can't find the gcd some other slicker way.

Thanks for pointing that out, I had completely forgotten about it. I'm wondering if you could have a quick look at something else for me? I'm pretty sure I know what I'm doing, but having your approval is re-assuring.

This : https://www.physicsforums.com/showthread.php?t=639142
 

1. What is number theory?

Number theory is a branch of mathematics that deals with the properties and relationships of numbers, particularly integers. It involves studying patterns and structures within numbers and their interactions with one another.

2. What are some common proofs in number theory?

Some common proofs in number theory include Euclid's proof of the infinitude of prime numbers, the proof of the irrationality of √2 by Pythagoras, and the proof of Fermat's Last Theorem by Andrew Wiles.

3. How do you prove a theorem in number theory?

In general, a theorem in number theory is proved using deductive reasoning and logical arguments. This involves starting with a set of assumptions or axioms and using mathematical techniques such as induction, contradiction, or direct proof to show that the theorem is true for all possible cases.

4. What is the significance of prime numbers in number theory?

Prime numbers, which are only divisible by 1 and themselves, play a crucial role in number theory. They are the building blocks of all natural numbers and have unique properties that make them important in cryptography, coding theory, and other areas of mathematics.

5. Can number theory be applied to real-world problems?

Yes, number theory has many practical applications in fields such as computer science, engineering, and physics. For example, number theory is used in cryptography to ensure secure communication, and in coding theory to efficiently transmit data. It also has applications in the design of algorithms and data structures.

Back
Top