Help with prime factorization proof

Click For Summary

Discussion Overview

The discussion revolves around a proof concerning prime factorization, specifically addressing the statement that if the product of two integers \( ab \) is divisible by a prime \( p \), and one of those integers \( a \) is not divisible by \( p \), then the other integer \( b \) must be divisible by \( p \). Participants explore the implications of the greatest common divisor and the use of integer combinations in the proof process.

Discussion Character

  • Technical explanation
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant expresses uncertainty about the meaning of \( (a,p)=1 \) and seeks clarification on its implications for the proof.
  • Another participant explains that \( (a,p)=1 \) indicates that the greatest common divisor of \( a \) and \( p \) is 1.
  • A participant suggests that since \( ab \) has a factor \( p \) and \( a \) does not, it logically follows that \( b \) must have the factor \( p \).
  • Another participant introduces a more complex example involving the integers \( \sqrt{5} \) and discusses the implications of prime factorization in different number systems.
  • One participant attempts to clarify the proof by stating that since \( p \) divides \( tpb \) and \( sab \), it follows that \( p \) divides \( b \), but this reasoning is not universally accepted.
  • Several participants engage in a light-hearted exchange about the relevance of older threads and the nature of the discussion.
  • There is a suggestion that the initial statement may not be true, but it is unclear what specific aspect is being questioned.

Areas of Agreement / Disagreement

Participants express a mix of agreement and disagreement regarding the proof and its implications. While some support the logical reasoning behind the proof, others raise questions about its validity and the assumptions involved.

Contextual Notes

Some participants reference the need for clarity on the division algorithm and its applicability in different mathematical contexts, indicating that the discussion may be limited by assumptions about the number systems being considered.

Ed Quanta
Messages
296
Reaction score
0
I have to prove that if ab is divisible by the prime p, and a is not divisible by p, then b is divisible by p.

In order to prove this, I have to show (a,p)=1. I am not sure what this statement means.

Then I am supposed to use the fact that 1=sa + tp when s,t are elements of the set of integers. (This statement was already proved in class). Then I figured to multiply across by b so that we get

b= sab + tpb. I am not sure where to from here. I have not seen to many proofs regarding prime factorization. Thanks

Ed
 
Physics news on Phys.org
(a,p)=1

This means "The greatest common divisor of a and p is 1". You may have sometimes seen this written as gcd(a, p) = 1.



b= sab + tpb

Well, you want to know if p divides the LHS of this, and the LHS is equal to the RHS...
 
Originally posted by Ed Quanta
I have to prove that if ab is divisible by the prime p, and a is not divisible by p, then b is divisible by p.

In order to prove this, I have to show (a,p)=1. I am not sure what this statement means.

Then I am supposed to use the fact that 1=sa + tp when s,t are elements of the set of integers. (This statement was already proved in class). Then I figured to multiply across by b so that we get

b= sab + tpb. I am not sure where to from here. I have not seen to many proofs regarding prime factorization. Thanks

Ed

If ab has a factor p and a don't, then b has the factor. That's logic.

If a = c + id and b = e - id, it's a bit harder.
 
Last edited:
Every result in maths is 'just logic', surely.

To show there is some content, consider Z{sqrt(5)]

2 is prime

2 divides 4=(sqrt5 - 1)(sqrt 5 +1)

2 divides neither of the terms on the left as they are both prime too.

so it important that the division algorithm works in Z. Or was that reference to x+iy some indiction of something in the ring Z?
 
Last edited:
You are almost finished.

Ed Quanta said:
I have to prove that if ab is divisible by the prime p, and a is not divisible by p, then b is divisible by p.

In order to prove this, I have to show (a,p)=1. I am not sure what this statement means.

Then I am supposed to use the fact that 1=sa + tp when s,t are elements of the set of integers. (This statement was already proved in class). Then I figured to multiply across by b so that we get

b= sab + tpb. I am not sure where to from here. I have not seen to many proofs regarding prime factorization. Thanks

Ed

Since you have already arrived at b=sab +tpb, we know that p divides tpb, and p divides sab so that p divides b.

If there seems a need here for steps, we can look at p(sab/p +tb) =b. Since we know (sab/p +tb) is an integer, we see that b contains the factor p.
 
Last edited:
Do you enjoy necromancing threads that are months old or something? :P
 
Perhaps it's not true?
 
Muzza said:
Do you enjoy necromancing threads that are months old or something? :P
I hoped I wasn't doing any harm. As for as good, well, I don't know. I thought it added for completeness.
 
Oh no, I was just kidding around when I said that.
 
  • #10
Sariaht said:
Perhaps it's not true?

Perhaps WHAT'S not true?
 

Similar threads

  • · Replies 5 ·
Replies
5
Views
3K
  • · Replies 17 ·
Replies
17
Views
2K
  • · Replies 31 ·
2
Replies
31
Views
4K
Replies
48
Views
7K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 17 ·
Replies
17
Views
3K
  • · Replies 21 ·
Replies
21
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 12 ·
Replies
12
Views
2K
  • · Replies 9 ·
Replies
9
Views
3K