Why Can't d Be a Perfect Square in Pell Equations?

  • Thread starter Thread starter cragar
  • Start date Start date
cragar
Messages
2,546
Reaction score
3

Homework Statement


A pell equation is an equation x^2-dy^2=1 where d is a positive integer that is not a perfect square. Can you figure out why we do not want d to be a perfect square?

The Attempt at a Solution


if d was a perfect square then we would have
x^2-d^2y^2=1 z=dy then x^2-z^2=1=(x+z)(x-z)=1
x>z for this to work so if x>z then x-z is at least 1 and then x+z would be bigger than 1
so (x+z)(x-z)>1 so this won't work so d can't be a perfect square. Does this work?
 
Physics news on Phys.org
hi cragar! :wink:

yes, that's ok :smile:

(though i'd be inclined to say that the only divisors of 1 are 1 and 1,
or -1 and -1, so x+z = x-z, so z = 0 and x = 1)
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top