• Support PF! Buy your school textbooks, materials and every day products Here!

Number Theory: Divisibility Proof

  • Thread starter tylerc1991
  • Start date
  • #1
166
0

Homework Statement



Show that if [itex]p[/itex] is an odd prime of the form [itex]4k + 3[/itex] and [itex]a[/itex] is a positive integer such that [itex]1 < a < p - 1[/itex], then [itex]p[/itex] does not divide [itex]a^2 + 1[/itex]

Homework Equations



If [itex]a[/itex] divides [itex]b[/itex], then there exists an integer [itex]c[/itex] such that [itex]ac = b[/itex].

The Attempt at a Solution



We have to do this proof by contradiction, so suppose [itex]p[/itex] divides [itex]a^2 + 1[/itex]. Then there exists an integer [itex]c[/itex] such that [itex]pc = a^2 + 1[/itex]. At this point I am stuck. I can't factor anything, and I don't see any other algebraic manipulations that will help. Any ideas?
 

Answers and Replies

  • #2
44
0
hbR0b.jpg
 

Related Threads on Number Theory: Divisibility Proof

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
621
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
2
Views
1K
Replies
1
Views
4K
  • Last Post
Replies
4
Views
1K
Replies
2
Views
3K
Replies
2
Views
879
Replies
3
Views
1K
Top