Is n^2 congruent to 0 or 1 (mod 3) for any integer n?

  • Context: Undergrad 
  • Thread starter Thread starter phyguy321
  • Start date Start date
  • Tags Tags
    Arithmetic
Click For Summary
SUMMARY

The discussion confirms that for any integer n, n^2 is congruent to either 0 or 1 modulo 3. This conclusion is derived from analyzing the squares of integers from 1 to 9 modulo 3 and considering the properties of numbers in base 3. Specifically, squares of integers can only yield remainders of 0 or 1 when divided by 3, as demonstrated through both even and odd cases of n. The proof is solidified by examining the congruence relationships and the behavior of squares in modular arithmetic.

PREREQUISITES
  • Understanding of modular arithmetic
  • Familiarity with congruences and their properties
  • Basic knowledge of even and odd integers
  • Concept of base representation in number theory
NEXT STEPS
  • Study the properties of modular arithmetic in greater depth
  • Explore the concept of quadratic residues modulo n
  • Learn about the application of congruences in number theory
  • Investigate the behavior of squares in different bases
USEFUL FOR

Mathematicians, students studying number theory, and anyone interested in modular arithmetic and its applications.

phyguy321
Messages
45
Reaction score
0
proof:
n^2 congruent 0 or 1 (mod3) for any integer n
 
Physics news on Phys.org
Try considering the two cases where n^2is either even or odd and how that relates to the congruence modulo 3.
 
Two other methods:

Consider just the squares of the integers from 1 to 9 modulo 3. Then you could generalize to higher numbers since powers of 10 are congruent to 1 (mod 3).

Or, consider a number in base 3. It can end in 0, 1 or 2. Thus a square in base 3 can only end in 0^2 = 0, 1^2 = 1, or 2^2 = 4 = 1 base 3. So a square in base 3 can only end in 0 or 1, which is equivalent to the square leaving a remainder of 0 or 1 upon division by 3.
 
Going along with what jeffreydk said, if n is an odd integer, what form does it have? what about if n is an even integer?
 

Similar threads

Undergrad Can integers be defined as N[[sqrt(1)]]?
  • · Replies 25 ·
Replies
25
Views
2K
Undergrad Question on Primitive Roots and GCDs
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Congruence for Symmetric and non-Symmetric Matrices for Quadratic Form
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Fundamental theorem of arithmetic from Jordan-Hölder theorem
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad ##S_{n}(\alpha)=\sum_{k=1}^{n} (-1)^{\lfloor{k\alpha\rfloor}}##
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Modulo and Modulus in math and computer programming
  • · Replies 5 ·
Replies
5
Views
3K
For n>3, show that the integers n, n+2, n+4 cannot all be prime
  • · Replies 27 ·
Replies
27
Views
3K
High School How Many Non-Congruent Triangles with Integer Sides Can a Given Perimeter Form?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Base Pi Integers: Isomorphism with Rationals?
  • · Replies 33 ·
2
Replies
33
Views
4K
Undergrad How Can You Find 'y' When ((m*y) mod n) ≡ (n-1)?
  • · Replies 2 ·
Replies
2
Views
4K