Find Perfect Squares from Residues Mod 16

Continuing that way (or, more easily, using a calculator) you will find that the only perfect squares mod 16 are 0, 1, 4, and 9.In summary, X mod m is the remainder when x is divided by m, and this value is called a residue. To find all perfect squares from the set of residues mod 16, simply square each residue and find the remainder mod 16. The only perfect squares mod 16 are 0, 1, 4, and 9.
  • #1
Bernie Hunt
19
0

Homework Statement



X mod m is the remainder when x is divided by m. This value is called a residue. Find all perfect squares from the set of residues mod 16.

The Attempt at a Solution



There was a suggestion that this would become clearer when the definition of perfect square was reviewed and found to be more than just a square rootable number.

I can't find a better definition of a perfect square than a number that has a square root that is an integer. Can anyone point me to an exhaustive definition of a perfect square?

Thanks,
Bernie
 
Physics news on Phys.org
  • #2
You have it. Let A be some system of arithmetic - the integers, or the integers mod m.

s in A is a square if s=r^2 for some r in A.
 
  • #3
Matt,

Thanks for the reply. One bit of clarification;

a and b are integers and a^2 = b

Is a the perfect square?

So if I was asked to find the perfect square of b, then the answer would be a?

Sorry for all the questions, but I'm struggling with the english syntax of this problem. I guess Shaw was right when he said the US and England were sperated by a common language. Heck, NY and CA are separated by a common language, hahaha.

Bernie
 
  • #4
Erm, no there is no language separation here. Please reread what was written. I said s was a square (prefect, if you must) if s was equal/equivalent to r^2 for some r. So, if all else fails, to find the squares mod 16, all you need to do is take the 16 residues, 0,1,..,15 and square them all and see what you get. In fact that is probably the most sensible way to do the problem.
 
  • #5
Thanks Matt!

I got it figured out. Along the way I also figured out there are many wrong definitions on the net for perfect squares, hahahaha.

Bernie
 
  • #6
Bernie Hunt said:

Homework Statement



X mod m is the remainder when x is divided by m. This value is called a residue. Find all perfect squares from the set of residues mod 16.
There are exactly 16 members of the set of residues mod 16, 0 through 15.
Square each of them and find the residue mod 16. For example, 22= 4 mod 16 so 4 is a perfect square mod 16. 32= 9 mod 16 so 9 is a perfect square mod 16. The "mod" part doesn't come in until you get numbers whose square is greater than 16: 52= 25= 16+ 9 = 9 mod 16 so that just gives you "9 is a perfect square mod 16" again. 62= 36= 2(16)+ 4 so "4 is a perfect square mod 16" again.
 

1. What is the purpose of finding perfect squares from residues mod 16?

The purpose of finding perfect squares from residues mod 16 is to identify patterns and relationships between numbers that are congruent to each other. This can be useful in various fields of mathematics, such as number theory and cryptography.

2. How do you find perfect squares from residues mod 16?

To find perfect squares from residues mod 16, you can use the formula (n^2) mod 16, where n represents any integer. This formula will give you the remainder when n^2 is divided by 16, and if the remainder is 0, then n^2 is a perfect square.

3. Can you explain the concept of residues mod 16?

Residues mod 16 refers to the set of numbers that are obtained when a larger number is divided by 16. These numbers are called residues and are represented by the remainder of the division. For example, the residues of 17 mod 16 would be 1, since 17 divided by 16 leaves a remainder of 1.

4. What is the significance of using mod 16 in finding perfect squares?

The use of mod 16 in finding perfect squares allows us to focus on a specific set of numbers that share congruency properties. This can help us identify patterns and relationships between numbers that may not be apparent when looking at the numbers as a whole.

5. Are there any real-world applications for finding perfect squares from residues mod 16?

Yes, there are several real-world applications for finding perfect squares from residues mod 16. For example, this concept is used in cryptography to generate secure keys and codes. It is also used in computer programming to optimize algorithms and improve efficiency.

Similar threads

  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
5K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
12
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
Replies
6
Views
2K
  • Science and Math Textbooks
Replies
10
Views
2K
Back
Top