Elementary number theory - prove the following statements

  • Thread starter Amcote
  • Start date
  • #1
16
0
This is my first time posting anything on the forum so I apologize if I do anything wrong. I have enrolled myself into elementary number theory thinking we would be taught how to do proofs however it is apparently expected that we already know how to do this. And so since I am a beginner at this, it would be very nice for someone to point out whether I'm doing/presenting the problems incorrectly or inefficiently.

Prove the following statements:

1) If p≥5 is a prime number, then p[itex]^{2}[/itex]+2 is a composite number.

Attempt:

I know that any prime number p>3 will have the form of either 6k+1 or 6k-1, and so I am able to put 6k-1 into the equation

(6k-1)[itex]^{2}[/itex]+2

36k[itex]^{2}[/itex]-12k+1+2

3(12k[itex]^{2}[/itex]-4k+1).

Similarly I substitute 6k+1 into the same equation with the result

3(12k[itex]^{2}[/itex]+4n+1)

thus showing that p[itex]^{2}[/itex]+2 is indeed a composite number.

Have I gone about this the right way?

2)
If a and 8a-1 are prime, then 8a+1 is composite.

Attempt:

I have been stuck on this one as I'm not really sure where to begin. The one thing I can think of doing is starting with a counter example.

Suppose a and 8a-1 are composite, this tells me (I think) that there is d|a such that 1<d<a and also c|8a-1 such that 1<c<8a-1, this is about as far as I have come and I'm not really sure how to proceed.

Any sort of help or hints would be great.

Thanks!
 

Answers and Replies

  • #2
AlephZero
Science Advisor
Homework Helper
6,994
291
Your logic in part 1 is fine. The presentation could be a bit shorter, for example

Any prime number p>3 will have the form of either 6k+1 or 6k-1.

If p = 6k-1, then
p2+2 = (6k-1)2+2
...
= 3(12k2-4k+1)
so p+2 is conposite.

Similarly if p = 6k+1 ,
p2+2 = 3(12k2+4n+1)
which is composite.

For part 2, try the same idea again. Let a = 6k+1 or 6k-1, and see what you get for 8a+1 and 8a-1
 
  • #3
16
0
Thank you for your quick response,

Now using your idea:

If a is prime, it will have the form either 6k+1 or 6k-1 so,

8(6k-1)-1 should be prime as well but,
48k-8-1=48k-9=3(16k-3) this is composite so the form 6k-1 does not work.

but

8(6k+1)-1=48k+8-1=48k+7 is it sufficient to say that 48k+7 is not composite?

If it is, then 6k+1 is an acceptable form so,

8(6k+1)+1=48k+9=3(6k+3) which is composite and is what we were trying to prove.

I feel like I've over assumed something during this proof.
 
  • #4
AlephZero
Science Advisor
Homework Helper
6,994
291
That proof is OK.

You know a = 6k-1 or 6k+1.
You showed a can't= 6k-1 because 8a-1 is composite.
So a = 6k+1.
You then showed if a = 6k+1, 8a+1 is always composite.
So if a = 6k+1 and also 8a-1 is prime, 8a+1 is always composite.
Of course for some primes of the form a = 6k+1, both 8a-1 and 8a+1 are composite, but that doesn't make your proof wrong. The theorem doesn't say anything about primes when 8a-1 is composite.

You forgot one small thing. In part one you said (correctly) that any prime > 3 is of the form 6k-1 or 6k+1. So you also have to show the theorem is true if a = 2 or a = 3, by just doing the arithmetic.
 
  • #5
16
0
Thank you very much for your help, it's much appreciated. (:
 

Related Threads on Elementary number theory - prove the following statements

Replies
3
Views
2K
Replies
6
Views
1K
  • Last Post
Replies
10
Views
1K
Replies
1
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
928
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
1K
Replies
2
Views
2K
Top