8 Replies - 1257 Views - Last Post: 06 September 2016 - 02:06 PM

#1 Brokenprogrammer  Icon User is offline

  • D.I.C Head

Reputation: 21
  • View blog
  • Posts: 113
  • Joined: 05-January 16

Tips for working with prime numbers & proofs

Posted 03 September 2016 - 02:48 AM

Hello, i have recently started my studies for Computer Science and i am working with the first math course. We are not allowed to use any tools like calculators etc which makes Math more interesting but a lot harder for someone that is not that good at it like me.

Anyway i have some problems which i wonder if you guys here on D.I.C. can help me with by giving me tips for how to solve and how to think.

1. Knowing if a number is a prime.
- A prime number is a number that can only be divided by itself or 1. But how can i without testing all numbers from 2...n know in a quick way if a number is prime or not? How do you guys do?

Example task: Which of the following numbers are prime numbers: 171, 203, 211, 221?

2. Prime factorisation of big numbers.
Example task: Do a prime factorisation of a) 24^4 and B) 250^3
This one i do not really have a good idea on how to tackle. Do i have to get the number that for example 24^4 represents or can i factorize it just from its exponential form?

3. Proofs
- I have had this tas which i have tried to solve for over 2 hours and I'm completely stuck.
Task: Proove that 6 | n(n^2-1) for any integer n
I have came so far that i can put n(n^2-1) = 6 * x according to the division laws a|b a = b * c
Then i can change the form of n(n^2-1) to n * (n+1)(n-1) or n^3 - n but I'm not sure which way to go or how to solve this one.
If i change it to n^3 - n = 6 * x i can move the -n to the other side and get n^3 = 6 * x+n but it doesn't get me closer to proving its divisable with 6.

I think what i have to do is make a variable for example b like i could do with for example a-1 = 4b then a = 4b+1 but i cannot wrap my head around this problem and its driving me nuts. Any help or pushes in the right direction is appreciated!

Sorry for bad formatting this was written from my phone.

Thanks

This post has been edited by Brokenprogrammer: 03 September 2016 - 02:55 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Tips for working with prime numbers & proofs

#2 andrewsw  Icon User is online

  • lashings of ginger beer
  • member icon

Reputation: 6333
  • View blog
  • Posts: 25,541
  • Joined: 12-December 12

Re: Tips for working with prime numbers & proofs

Posted 03 September 2016 - 03:01 AM

For the first question, it is not a question of how we guys do it, there are known and proven algorithms for determining whether a number is prime. Presumably, your book covers this? Otherwise, it is off to the internet!

Primality test

Similarly, for question 2, you need to find and research information about these things. How else are you going to complete the tasks? If you, are anyone else, can invent their own methods for these things then they should probably be writing the book!

Of course, it is still very beneficial to consider the questions and reason out possible solutions, or approaches, yourself. As you progress you will then, of course, be able to use the knowledge and theorems that you have acquired earlier in the course, to help tackle further problems.
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: Tips for working with prime numbers & proofs

Posted 03 September 2016 - 06:38 AM

Moved to Computer Science.

For part (3), observe that n-1, n, n+1 are three consecutive numbers. So one of them is a multiple of three. Hence, 3|(n-1)n(n+1).
Was This Post Helpful? 1
  • +
  • -

#4 jon.kiparsky  Icon User is online

  • Screw Trump (before he screws you)
  • member icon


Reputation: 10622
  • View blog
  • Posts: 18,174
  • Joined: 19-March 11

Re: Tips for working with prime numbers & proofs

Posted 03 September 2016 - 12:26 PM

Quote

But how can i without testing all numbers from 2...n know in a quick way if a number is prime or not? How do you guys do?


It's much more fun to figure this stuff out than to look it up or to have the answer handed to you. Takes longer, but it's totally worth it.

So, let's think more about what it means for a number to be prime. It means that there are no factors of the number other than itself and 1. Now let's suppose that we know how to check divisibility, but it takes time. (this is in fact true) So one approach to this problem is to limit the set of potential factors that we have to examine, to minimize the work we have to do in order to answer the question.

So we've transformed the problem from a vague cry for help ("how can I do this?") to one that we can reason about: how can we characterize the set of numbers we need to examine in order to determine whether a given number is prime? From there, I would probably start brainstorming: what sorts of numbers can we remove from consideration right off the bat, and why? It's useful to think in terms of concrete numbers, like 256 or 1311 or 45, and then to generalize your thoughts to abstractions like "n".
Was This Post Helpful? 2
  • +
  • -

#5 Brokenprogrammer  Icon User is offline

  • D.I.C Head

Reputation: 21
  • View blog
  • Posts: 113
  • Joined: 05-January 16

Re: Tips for working with prime numbers & proofs

Posted 05 September 2016 - 09:44 AM

After quite some time i think i managed to solve the (3rd) problem.

As macosxnerd101 said (n-1)n(n+1) is three consecutive numbers. This gives us the information that atleast one of the three numbers has to be divisible with 3 and one of the numbers has to be even which makes atleast one divisible with 2.

The 6 which we should use to check if 6 | n(n^2 - 1) can be factorized into 2*3 which if we translate into the definition of divisors (If a | b then there is a integer so that a = b * c) it should look like n(n^2 - 1) = 2 * 3 * x were x is an integer.

One thing i also think is hard with proofs is to know when to stop. But i think i got it right here, please do help me if my solution is wrong.

There is loads of studies right now so i will try to post all my solutions to the problems as i have time to dig deeper and tackle them.

This post has been edited by Brokenprogrammer: 05 September 2016 - 09:44 AM

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: Tips for working with prime numbers & proofs

Posted 05 September 2016 - 09:52 AM

Quote

The 6 which we should use to check if 6 | n(n^2 - 1) can be factorized into 2*3 which if we translate into the definition of divisors (If a | b then there is a integer so that a = b * c) it should look like n(n^2 - 1) = 2 * 3 * x were x is an integer.

If we have three consecutive numbers, at least one of them is even, right? And we have already deduced one of them is divisible by 3. So you can factor out 6 from n(n+1)(n-1) and you are done.
Was This Post Helpful? 0
  • +
  • -

#7 Brokenprogrammer  Icon User is offline

  • D.I.C Head

Reputation: 21
  • View blog
  • Posts: 113
  • Joined: 05-January 16

Re: Tips for working with prime numbers & proofs

Posted 05 September 2016 - 09:57 AM

So what i did is considered too much or what would you say about the solution i presented?
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: Tips for working with prime numbers & proofs

Posted 05 September 2016 - 02:47 PM

It wasn't clear if this:

Quote

The 6 which we should use to check if 6 | n(n^2 - 1) can be factorized into 2*3 which if we translate into the definition of divisors (If a | b then there is a integer so that a = b * c) it should look like n(n^2 - 1) = 2 * 3 * x were x is an integer.


Was a question or a statement.

You should be concise and direct in your statements. Then from prior statements, deduce new facts. If I were writing this up, I would write it as follows:

Quote

Observe that n(n^2 - 1) = n(n-1)(n+1), which is the product of three consecutive numbers. Thus, 3 divides either n-1, n, or n+1. Let q be an integer such that 3q = n(n-1)(n+1). We similarly deduce that at least one of n-1, n, or n+1 must be even, so 2 divides n(n-1)(n+1) = 3q. As 2 and 3 are distinct prime numbers, we apply Euclid's Lemma to deduce that 2 divides q. Let k be an integer such that 2k = q. So 3q = 3(2k) = 6k = n(n-1)(n+1). So 6 divides n(n-1)(n+1). QED.


Get in the habit of applying the definitions and showing why you can utilize certain theorems. This way, when you read your work, you can see exactly the line of reasoning or where you went wrong. It is not appropriate or helpful at this stage to omit details in your proofs, so don't leave out things which you may think are obvious.
Was This Post Helpful? 0
  • +
  • -

#9 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: Tips for working with prime numbers & proofs

Posted 06 September 2016 - 02:06 PM

Quote

1. Knowing if a number is a prime.

Based on what you have shown, it doesn't look like you are going to be dealing with large primes so figuring out if a number is prime should be manually manageable. As Jon hinted, you don't need to test all numbers from 2 to n. I would suggest you take a prime number and start dividing from 2 to n, but don't just discard the results. Look at the pattern of the results and try to figure out when you can confidently stop testing and why.

Quote

2. Prime factorisation of big numbers.

Again, these numbers seem small and managable. Keep in mind that if you have a number (a^x*b^y)^5 then you can multiply the outer exponent by the inner exponent to get a^5x * b^5x. So, to find the prime factorisation of 24^4, we find the prime factorisation of 24 and then multiply the exponents by 4.
24 = 2^3 * 3, so 24^4 = 2^12 * 3^4

This post has been edited by mojo666: 06 September 2016 - 02:07 PM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1