3

I'll try in $\to$ direction;

Nothing divides the prime $p$ but $\pm1, \pm p$. If $a = \pm p$ or $a = \pm 1$ then $p \mid a$.

Assume $p = 2$ . If $a$ is even, then $p \mid a$ and if $a$ is odd, then $(a, p) = 1$.

Suppose $p > 2$. If $a$ is even, then $(a, p) = 1$ since $2$ is the only even prime integer. Suppose $a$ is odd. Then $a$ is either prime or not. If $a$ is prime, then $(a, p) = 1$. If $a$ is not prime, then $a$ is either positive/negative multiple of $p$ or not. If it's the former $p \mid a$, otherwise $(a, p) = 1$.

How can I improve it?

user266485
  • 31
  • 1
    Your statement " If a is even, then (a,p)=1 since 2 is the only even prime integer." is false. Take $p=3$ and $a = 6$. – lulu Sep 02 '15 at 21:13
  • In that case do we say either $a$ is a multiple of $p$ or not? Is there a better, more compact proof? – user266485 Sep 02 '15 at 21:16
  • 1
    I'll do the $\Rightarrow$ direction, leave the other to you. Suppose $p$ is a prime. Then, look at $(a,p)$. of course, we have $(a,p)|p$ and since $p$ is prime that means that $(a,p)$ is either $1$ or $p$. If it is $1$ we are done, so say it is $p$. But of course we also have $(a,p)|a$ so this would mean $p|a$ so again we are done. – lulu Sep 02 '15 at 21:22
  • Very nice. I had another thought. If $p \mid a$, we are done. Suppose $p$ doesn't divide $a$. Let $q \neq p \in \mathbb Z$ such that $q \mid a$. But then $q$ doesn't divide $p$, so $(a, p) = 1.$ Would something like that work? – user266485 Sep 02 '15 at 21:34
  • You are trying to prove $\Leftarrow$ now? – lulu Sep 02 '15 at 21:40
  • No. I was just trying to see what else I could do in $\to$ direction in addition to what you wrote. – user266485 Sep 02 '15 at 21:41
  • Never mind, I see you are trying for another proof of $\Rightarrow$. But, I don't think it works. What is $q$ ? you need an argument for all $a$ not just primes. – lulu Sep 02 '15 at 21:42
  • Ok...I see what you are saying. If you know Unique Factorization, you can reason this way. Fair enough. – lulu Sep 02 '15 at 21:43
  • Than you very much, lulu. I'll go try the other direction. – user266485 Sep 02 '15 at 21:45
  • If $(a, p) = 1$, then $p$ is not necessarily prime because $(9, 4) = 1$. If $p \mid a$ and $p$ is prime we're done. Suppose $p$ is composite. Then $a$ can't be prime, so $a$ is composite. But then we can reduce both $p, a$ to their prime versions. So $p$ is prime. ? – user266485 Sep 02 '15 at 23:17
  • Not following. My sense is that in this direction ($\Leftarrow$) it is easier to prove the contrapositive. That is, given that we want to show $A\Leftarrow B$ prove instead that $not,B\Leftarrow not,A$ Therefore, assume that $p$ is not a prime. Find an $a$ such that neither $p|a$ nor $(a,p)=1$. – lulu Sep 03 '15 at 00:44
  • How about this: Let $ax + py = 1$. Then $pax + ppy = p$. Since $p \mid a$, we have $p | pax$ and since $p \mid p$, we have $p \mid ppy$. Further, $p \mid (pax + ppy)$. So, $p \mid p$. So then $p$ must be prime. – user266485 Sep 03 '15 at 01:00
  • What are you assuming here? It looks like you are saying that BOTH $(a,p)=1$ and $p|a$. That is not possible. If $p|a$ then $(a,p)=p$. – lulu Sep 03 '15 at 01:04
  • All you need to prove is this: if $p>1$ is not a prime, then there is at least one number $a$ such that neither $(a,p)=1$ nor does $p|a$. Try an example. Suppose $p=6$..Can you find an $a$ that works in this particular case? – lulu Sep 03 '15 at 01:08
  • Can we let $a = 3$? – user266485 Sep 03 '15 at 01:21
  • Absolutely. Good. Can you now do the general case? – lulu Sep 03 '15 at 01:22
  • So we showed the second part is true for $p > 1$. Can we say since $p > 1$ is prime $-p < -1$ is also prime? – user266485 Sep 03 '15 at 01:26
  • Not really. I think the problem only makes sense for positive $p$. That is, you are meant to be showing that $|p|$ is prime. It's a bad idea to let negative numbers be prime...messes up Unique Factorization, for example. As $6=2^3=(-2)^(-3)$. – lulu Sep 03 '15 at 01:34
  • Ok, I might've misunderstood you. What's general case? Didn't we show p is prime? – user266485 Sep 03 '15 at 01:37
  • We showed $6$ didn't work! but now you have to repeat the argument for every composite $p$. How to do that may be clear to you at this point, but I didn't see it written out. – lulu Sep 03 '15 at 01:39
  • I failed to find such $a$. $(a, p) = 1$ means $a \neq \pm 1, \pm p$ doesn't divide $p$. So, the only integers that divide $p$ are $\pm 1, \pm p$, but isn't that the definition of prime? – user266485 Sep 03 '15 at 03:38
  • Well, look at what worked for $6$. You chose $a=3$, a factor of $6$. Similarly, if $p$ is not a prime, then we can write $p=m^*n$ for integers $m,n>1$. Try one of those. – lulu Sep 03 '15 at 11:04
  • Let $a = m$. Then $(a, p) = m$ and $p$ doesn't divide $a$. Seems like we're done? – user266485 Sep 03 '15 at 12:41
  • That works. Good! – lulu Sep 03 '15 at 12:57

1 Answers1

1

As requested, here is a summary of the argument sorted out in the comments.

We will take $p>1$. If $p<-1$ then the arguments below show that $|p|$ is a prime, which is what I assume the question intends.

First, let's show $p$ prime $\Rightarrow$ either $(a,p)=1$ or $p|a$

Pf: We will use the fact that, for any integers $m,n$ $(m,n)|m$ and $(m,n)|n$. In this case, we note that $(a,p)|p\Rightarrow (a,p)=1\;or\;(a,p)=p$. In the first case, we are done at once. In the second we are done once we note that $(a,p)|a$.

Now, the opposite implication.

Pf: It is easier to show the contrapositive, so suppose that $p$ is not a prime. We need to show that the right hand statement is false. We write $p=mn$ where $m,n$ are integers, both greater than $1$. Then taking $a=m$ gives the desired contradiction and, again, we are done.

lulu
  • 70,402