Can You Solve These Prime Number Proofs?

  • Thread starter Thread starter JdotAckdot
  • Start date Start date
  • Tags Tags
    Prime Proofs
JdotAckdot
Messages
4
Reaction score
0
Just a couple questions that I'd appreciate any help on.

1. if [(2^d) - 1] is prime, prove that d is prime as well.

2. Prove that (p-1)C(k) is congruent to (-1)^k mod p.

I've started them both but ended up getting stuck.
Any ideas?

Thanks
 
Physics news on Phys.org
1. These look like textbook questions and so should go into the appropriate section of the Science Education Zone.

2. To get help, you must first show what you've tried and where you're stuck.
 
JdotAckdot said:
I've started them both but ended up getting stuck.
Any ideas?

Yes, show us how you started and where you got stuck. The responses by CarlB and AKG have been "soft deleted" and will be restored once you have shown an attempt at the problem.
 
first Q is simple

if d is even .2^d is 2^2n .even no: are {expressed in this form } ie 4^n if n is prime i.e. n>or=2 4^n is > or = 16. 4^n -1 is never a prime no. { eg 16-1=15}
so n cannot be even.thus we can prove by indirect method.
 
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