Help with prime factorization proof

In summary, Ed showed that if ab is divisible by the prime p, and a is not divisible by p, then b is also divisible by p. He is not sure what this statement means, but he uses the fact that 1=sa + tp when s,t are elements of the set of integers to get b. Finally, he shows that b=sab +tpb, and p divides tpb and p divides sab, so that b contains the factor p.
  • #1
Ed Quanta
297
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
  • #2
(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...
 
  • #3
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:
  • #4
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:
  • #5
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:
  • #6
Do you enjoy necromancing threads that are months old or something? :P
 
  • #7
Perhaps it's not true?
 
  • #8
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.
 
  • #9
Oh no, I was just kidding around when I said that.
 
  • #10
Sariaht said:
Perhaps it's not true?

Perhaps WHAT'S not true?
 

1. How do I find the prime factorization of a number?

To find the prime factorization of a number, you can use the process of repeated division. Start by dividing the number by the smallest prime number possible, and continue dividing the resulting quotients by prime numbers until all the factors are prime. The prime factorization is the product of all the prime numbers used in the division process.

2. What is the importance of prime factorization?

Prime factorization is important because it helps us understand the fundamental building blocks of a number. It also allows us to simplify fractions, find common factors or multiples, and solve problems related to divisibility and GCD (greatest common divisor).

3. Are there any shortcuts or tricks for finding prime factorization?

Yes, there are a few shortcuts that can make finding prime factorization quicker. One method is to use a factor tree, which involves continuously dividing the number into smaller factors until only prime numbers remain. Another method is to use a factorization wheel, which is a visual tool that helps identify the prime factors of a number.

4. How can I prove that my prime factorization is correct?

To prove the correctness of prime factorization, you can use the fundamental theorem of arithmetic, which states that every positive integer has a unique prime factorization. This means that no matter which method you use to find the prime factorization, the result should always be the same.

5. Can prime factorization be used on non-integer numbers?

No, prime factorization is only applicable to positive integers. Non-integer numbers like fractions, decimals, and negative numbers cannot be prime factorized because they do not have a unique set of prime factors. However, the concept of prime factorization can be extended to include prime factorization of polynomials in algebra.

Similar threads

  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
866
  • Linear and Abstract Algebra
Replies
11
Views
2K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
692
  • Precalculus Mathematics Homework Help
Replies
3
Views
900
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
Back
Top