Number Thry: Divisibilty, perfect square.

  • Thread starter mattmns
  • Start date
  • Tags
    Square
In summary: Since a perfect square is not of the form 3k+2 it must be of the form 3k+1 of 3k, for the former it is easy to see that p^2+2 is composite.But for the latter I am stuck again.Any ideas here?In summary, the question is asking for a number 3k that is the square of a prime greater than 4, and the answer is obviously not possible. The first part of the answer is that a can either be: a=1,2,-1 mod 3 => a^2=1 mod 3 or a can be: a=1,2,3,4,5,6,7,8
  • #1
mattmns
1,128
6
Here is the question:
-------------
Show that a perfect square is never of the form 3k+2 for any k. Conclude that if p is prime and [itex]p \geq 5[/itex], then [itex]p^2 + 2[/itex] is always composite.
-------------

We are at the very start of the book, so there is not very much available to use. We have defined a|b, primes, floor and ceiling (which I don't think will play a role here), and have the division theorem.

For the first part I think it is going to be proved by contradiction, so I have been trying to get some kind of parity going with both sides. I tried using [itex]n^2 - 1 = 3k+1[/itex] and then breaking into evens and odds, but that did not get anywhere. I was also trying to get a contradiction with [itex]3k+2 \mid n[/itex], but again was able to get nothing. Any ideas?

For the second part I was using the result of the first. Since a perfect square is not of the form 3k+2 it must be of the form 3k+1 of 3k, for the former it is easy to see that [itex]p^2+2[/itex] is composite. But for the latter I am stuck again. Any ideas here?

Thanks!
 
Physics news on Phys.org
  • #2
Can you have a number 3k that is the square of a prime greater than 4?
 
  • #3
Obviously not, otherwise the "prime" would be divisible by 3 :smile: That takes care of the second part, thanks!
 
Last edited:
  • #4
1) look at things mod 3.
a can either be:
a=1,2,-1 mod 3 => a^2=1 mod 3

2) use mod 3 again.
 
  • #5
Induction? Prove its not true for n=1, then n=k+1.
 
  • #6
tim_lou said:
1) look at things mod 3.
a can either be:
a=1,2,-1 mod 3 => a^2=1 mod 3
There's a tiny error there (should be a=0,1,2 mod 3)...but the method works.
 
  • #7
We can't techincally use mod, but the idea behind it is perfect for the proof, thanks for the idea, I got it all worked now :biggrin:
 

1. What is divisibility in number theory?

Divisibility is a fundamental concept in number theory that refers to the ability of one number to be divided evenly by another number without leaving a remainder. In other words, if a number is divisible by another number, it can be divided into equal parts without any leftovers.

2. How can I tell if a number is divisible by another number?

To determine if a number is divisible by another number, we can use the divisibility rules. For example, a number is divisible by 2 if the last digit is even, and it is divisible by 3 if the sum of its digits is divisible by 3. There are specific rules for each number, making it easier to determine divisibility.

3. What is a perfect square in number theory?

A perfect square is a number that is the result of multiplying a whole number by itself. In other words, it is the square of an integer. For example, 9 is a perfect square because it is the result of 3 multiplied by itself (3x3=9).

4. How can I determine if a number is a perfect square?

To determine if a number is a perfect square, we can take the square root of the number. If the square root is a whole number, then the original number is a perfect square. For example, the square root of 16 is 4, which is a whole number, so 16 is a perfect square.

5. What is the significance of divisibility and perfect squares in number theory?

Divisibility and perfect squares are essential concepts in number theory as they help us understand the properties and relationships between numbers. They also play a crucial role in solving mathematical problems and can be applied in various fields, such as cryptography, computer science, and engineering.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
3K
  • Calculus and Beyond Homework Help
Replies
5
Views
991
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
692
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Advanced Physics Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
774
Back
Top