Part (b). So, this is from the introduction of a discreet math book, How to Prove it, idk where to even start with this, and figure that since it's part of the 1st question in the intro that I should know how to do it. But, alas.
Take a closer look at the proof and conditions of conjecture 2 in chapter 1. It states that if you have a positive integer n that isn't prime (i.e it is n=ab for positive integers a and b both less than n, then the integer given by (2^n)-1 = (2^ab) - 1 is not prime either.
But the proof itself for that conjecture gives you a means of computing integer factors x and y of any such number where n is not prime. It uses the telescoping property of sums to prove in general under these conditions that:
(2^n) - 1 = ( (2^b) -1 ) * y
That is, one of the two factors you are looking for takes the form x = (2^b) - 1.
So let's use this to solve part (a) as an example. (2^15) -1 = 32767 is not prime according to conjecture 2 because 15=3*5, a product of positive integers less than n=15 . Now plug it into the equation with a = 3 and b = 5:
( ( 2^3*5 ) - 1 ) = ( (2^5) - 1 ) * y
Now you just solve for y:
y = ( ( 2^3*5 ) - 1 ) / ( ( 2^5 )- 1 ) = 1057
And we already had x = (2^5) -1 = 31
We may now easily confirm the result by multiplying: 1057 * 31 = 32767.
To apply this to part b, all that remains is to repeat the process with a = 31 and b = 1057.
๐
Thanks so much, that was super helpful!
You're very welcome! I'm slowly teaching myself what is essentially a mathematics undergrad degree, and I'm familiar with the book you're using, so if you ever have any other questions feel free to ask!
Word of advice: In most math books, especially at lower levels, the majority of the exercises will nearly always be some sort of direct application of the theorems and proofs in the preceding chapter of instruction.
So when you feel stuck, you should go back to those theorems and try to make sure you really understand what the proof is saying. Like try to be skeptical about the statements and examine them until you are fully convinced that the proof is ironclad. Then it'll be much easier to spot which theorems each exercise is meant to provide elaboration/nuance on, especially the earlier exercises in a chapter.
The later exercises in a chapter tend to be much more difficult, but you'll nearly always be able to prove them with the theorems you've already learned, it's just that the harder ones will be essentially foreshadowing theorems in future chapters. So the longer you stick with this, deeply examining every theorem and attempting every exercise, the easier it becomes as you begin to understand the pedagogical intent of the author.
Thanks so much! I will probably post more problems. I went back to school a few years ago and this was my next math class so I wanna work through it and think about maybe finishing my math BA, but also might just keep doing math for fun. ๐คทโโ๏ธ
~~32767 is suspiciously close to cubed 32, and first question implies that's important (if you've done it)~~ knowing factors from the first question, you can do some shenanigans close to the first question logic
spoiler
a^n^-b^n^
What do you know about Mersenne numbers?
Just a bit, but mostly from this chapter so far.