Proving the Primality of an Integer with a Specific Divisibility Property

  • Thread starter Thread starter Cableguy008
  • Start date Start date
  • Tags Tags
    Integer Prime
Click For Summary

Homework Help Overview

The discussion revolves around proving the primality of an integer \( p \) based on a specific divisibility property. The original poster is grappling with the implications of the property that if \( p \) divides the product of two integers \( b \) and \( c \), then \( p \) must divide at least one of them. The challenge lies in demonstrating that \( p \) must be prime, rather than merely showing that it can be prime.

Discussion Character

  • Conceptual clarification, Assumption checking, Mathematical reasoning

Approaches and Questions Raised

  • The original poster attempts to manipulate the conditions given in the problem using the greatest common divisor and various substitutions, but expresses confusion about reaching a conclusion. Some participants suggest exploring the implications of assuming \( p \) is not prime and using the hint provided in the problem statement. Others discuss the relationship between divisors and the implications of the divisibility property.

Discussion Status

The discussion is ongoing, with participants providing insights and exploring different interpretations of the problem. Some guidance has been offered regarding the implications of the hint, and there is a recognition of the need to clarify assumptions about the integers involved. The original poster acknowledges the assistance received, indicating a productive exchange.

Contextual Notes

There is a mention of the difficulty in working with integers as opposed to natural numbers, and a suggestion that \( p \) should be positive to align with the conventional definition of prime numbers.

Cableguy008
Messages
3
Reaction score
0
Hey there, I've been having some problems trying to prove this:

"Let p be an integer other than 0, +/- 1 with this property: Whenever b and c are integers such that p | bc, then p | b or p | c. Prove p is prime. [Hint: If d is a divisor of p, say p = dt, then p | d or p | t. Show that this implies d = +/- p or d = +/- 1.]"

Proving p *can* be prime isn't too difficult, but proving p *must* be prime has really confused me.

I've tried going down the path, gcd(p,b) = p if p | b. Which means p = pn + bm, but since b = px, p = pn + pxm = p(n + mx) => n + mx = 1. This doesn't seem to get me anywhere though.

Then I've tried using b = pn, c = pm and tried various manipulations such as b / n = c / m => bm = cn = pmn but I just don't see how I can get it in the form p = dt.

Now, if I got it to the form p = dt, I'm not sure how I could prove p must be prime. Who's to say its not prime? I don't know it seems like I'm thinking in circles here. (Sorry for not properly defining n,m and x I just assumed they were integers to save time). Any help would be greatly appreciated. Unfortunately my professor has been out of town for the entire week so I've been unable to seek help from him (its still due though of course :P).
 
Physics news on Phys.org
Suppose p is NOT a prime. Then p= mn for some integers m and n. Let b= m, c= n.

bc= mn is divisible by p but neither b nor c are.
 
Use their hint. If p=dt then you know p|d or p|t, assume it's the former. So p|d and d|p, which is larger in absolute value, d or p?
 
"Use their hint. If p=dt then you know p|d or p|t, assume it's the former. So p|d and d|p, which is larger in absolute value, d or p?"

Ok so since p = dt (or nm) p / d = t, since t is an int d | p. If p | d, d / p = 1 / t, so t = +/- 1 and thus d = +/- p. Conversely if p | t, WLOG t = +/- p, d = +/- 1. So d = +/- p or +/- 1 and p is prime. Is this correct?
 
Cableguy008 said:
"Use their hint. If p=dt then you know p|d or p|t, assume it's the former. So p|d and d|p, which is larger in absolute value, d or p?"

Ok so since p = dt (or nm) p / d = t, since t is an int d | p. If p | d, d / p = 1 / t, so t = +/- 1 and thus d = +/- p. Conversely if p | t, WLOG t = +/- p, d = +/- 1. So d = +/- p or +/- 1 and p is prime. Is this correct?

Looks good, though not exactly what I had in mind. If a|b then a<=b, etc (assuming a, b positive-it's such a pain to work with the integers instead of the naturals here, note there should also be a requirement that p is positive if you mean it to be a prime in the usual sense).
 
Thanks for the input you two, you've truly helped out.
 

Similar threads

High School Probability that 2 distinct integers are divisible by the same number
  • · Replies 9 ·
Replies
9
Views
3K
Graduate Prime Number Powers of Integers and Fermat's Last Theorem
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
7K
High School Proving Euclid's Lemma: The Role of Primality in Divisibility
  • · Replies 6 ·
Replies
6
Views
3K
Show that 13 is the largest prime that can divide....
  • · Replies 7 ·
Replies
7
Views
2K
Prove that there are infinitely many primes of the form ## 8k-1 ##
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
3K
Proving an integer problem about the sum of a square number and a prime number
  • · Replies 18 ·
Replies
18
Views
3K
Undergrad Localising a non integral domain at a prime
  • · Replies 17 ·
Replies
17
Views
3K
Proving Closure and Identity for U(n)
  • · Replies 16 ·
Replies
16
Views
5K