Math Is Fun Forum
You are not logged in.
- Topics: Active | Unanswered
#26 Re: This is Cool » Reducing the no. of potential factors for n^2+1. » 2016-10-29 14:23:16
It isn't particularly difficult to understand -- I can explain it to you if you just tell me what it is that you need help with.
I get the beginning but not the end of it where you've put (-1/p)=-1.
Just to make sure, this is what you want to know, correct?
-You are considering only numbers of the form any non-zero positive integer.
-You would like to know something about the prime factorisations of these numbers.
First point is correct but I just wanted to show that by using
we can reduce the number of possible factors which should help compute primes faster. And now you have shown that will never be factorable by the primes of the form so thank you. I thought about 50% of primes could not possibly be factors but now you're saying that not only would there be 50%, but that there would be a bias to more than 50% due to Chebyshev's bias. Have I got this right?I am also still trying to work out if there's anything else we can use this scenario for to do with primes. If there was a wheel of prime factors that could factor
, it would be 20m + 1 or 9 or 13 or 17, not including 2 and 5.#27 Re: This is Cool » Reducing the no. of potential factors for n^2+1. » 2016-10-28 07:39:32
You can immediately rule out any primes such that whenever is not itself prime.
But after you have ruled out primes where
all that is left are p's For instance n=12 =145 rule out/divide by 5 and you get 29, a primeYou can also rule out primes
by Euler's criterion (or more specifically, by the corollary I mentioned in my previous post).
I don't get Euler's criterion, and probably never will it's just too advanced for me, don't worry. So what you're basically saying is we can rule out possible prime factors where p=4m+3 for
?#28 Re: This is Cool » Reducing the no. of potential factors for n^2+1. » 2016-10-27 15:43:37
Primenumbers wrote:Potential factors for
may only be factored by previous values ofForgive my ignorance, but I have no idea what this means. Could you explain this?
Because.............
Let p= potential factor
Let p=n-y
(n-y)(n+y) =
Therefore remainder when is divided by p =And remainder when
is divided by p =That's correct. But I still don't know what a potential factor is (or what you need this part for).
y=n-x
y will be less than p because y=n-p and p>0
You mean y will be less than n, not p.
Yes
p will not be greater than n because we are only concerned with primes
So I am guessing by "potential factor" you mean "prime factor"? Also, assuming you want n^2 + 1 to be composite (which isn't true in general, as your next post shows), you need a ≤ sign.
Basically x<n because we are only concerned with factors below the square root, and because y=n-x, y cannot=n because x>0.
This should reduce potential factors for
You mean reduce the possibilities for the prime factors of n^2 + 1?
Yes
I have tried up to n=43. Prime factors <44 that were missing were 3, 7, 11, 19, 23, 31 and 43 which exactly halved the no. of potential prime factors. Any value for n to infinity will not be factorable by these no.'s.
then they will never occur because ones above p are just repeats of ones <p.
The factors repeat themselves every +p value for n. So if they don't occur beforeI still don't really understand what you are trying to do, from your post or from your examples in the post above. If you're wondering why 3, 7, 11, 19, 23, 31 and 43 don't appear in the prime factorisations of n^2 + 1, then this is because of quadratic reciprocity. (Let me know if you haven't come across this term before, and I'll be happy to explain it.) In other words, consider the congruence for p = 3 mod 4:
but this doesn't have any solutions, because if , then , where is the quadratic reciprocity symbol. (Which is just another way of saying that -1 isn't a square modulo p, where p is 3 modulo 4 -- in other words, the congruence has no solutions for p = 3 mod 4.)
Basically I am trying to make it so that instead of a computer having to try to factor all the primes below the square root for an integer, it only has to try and factor a lot less. Also because the factors repeat themselves this could make things easier. Maybe could do a wheel or something? No, I have never come across Euler' Criterion and I don't get it.
#29 Dark Discussions at Cafe Infinity » Martial Arts are completely useless » 2016-10-26 14:28:35
- Primenumbers
- Replies: 4
I was going to go to a Taekwondo class but then I found out online that martial arts are completely useless in a real fight apparently. And I wanted self-defence training.
As I thought about this I realised it was completely true..................
I am trained in Judo, (no punching and kicking), and my identical twin is one belt below black in karate. We had lots of fights when I was mentally ill and it would usually end in a standoff because we were both pretty evenly matched. I didn't use any of my throws or holds and that means my twin's brown belt in karate was useless against me who would actually be a white belt in karate. How amazing is that!
Apparently things like boxing, wrestling and MMA are better because you actually get hit and experience the real ruff-and-tumble of a real fight.
#30 Re: Help Me ! » solve » 2016-10-22 07:32:10
7 is prime so only factorable by 1 or 7.
the only squares less than 6 are 1 and 4 therefore a=1, r=2
a=7, r=0
73 is prime so only factorable by 1 or 73. 73 too big so must be 1. Only smaller than 73 is r= 1 or 2. 1 is too small so a=1, r=2.
#31 Re: This is Cool » Reducing the no. of potential factors for n^2+1. » 2016-10-20 23:22:31
Examples: [Formulas followed by prime factorization, as you can see factors 3,7,11,19,23,31 and 43 are missing]
n=1
n=2 5
n=3 10=2,5
n=4 17
n=5 26=2,13
n=6 37
n=7 50=2,5
n=8 65=5,13
n=9 82=2,41
n=10 101
n=11 122=2,61
n=12 145=5,29
n=13 170=2,5,17
n=14 197
n=15 226=2,113
n=16 257
n=17 290=2,5,29
n=18 325=5,13
n=19 362=2,181
n=20 401
n=21 442=2,13,17
n=22 485=5,97
n=23 530=2,5,53
n=24 577
n=25 626=2,313
n=26 677
n=27 730=2,5,73
n=28 785=5,157
n=29 842=2,421
n=30 901=17,53
n=31 962=2,13,37
n=32 1025=5,41
n=33 1090=2,5,109
n=34 1157=13,89
n=35 1226=2,613
n=36 1297
n=37 1370=2,5,137
n=38 1445=5,17
n=39 1522=2,761
n=40 1601
n=41 1682=2,29
n=42 1765=5,353
n=43 1850=2,5,37
#32 This is Cool » Reducing the no. of potential factors for n^2+1. » 2016-10-20 13:53:53
- Primenumbers
- Replies: 9
New Theorem:
Potential factors for
Because.............
Let p= potential factor
Let p=n-y
(n-y)(n+y) =
Therefore remainder when is divided by p =
And remainder when is divided by p =
y will be less than p because y=n-p and p>0
p will not be greater than n because we are only concerned with primes
This should reduce potential factors for
and reduce computing space for finding primes.I have tried up to n=43. Prime factors <44 that were missing were 3, 7, 11, 19, 23, 31 and 43 which exactly halved the no. of potential prime factors. Any value for n to infinity will not be factorable by these no.'s.
The factors repeat themselves every +p value for n. So if they don't occur before
#33 This is Cool » I think this is a new proof of Fermat's Last Theorem. » 2016-05-17 09:30:18
- Primenumbers
- Replies: 3
Fermat's Last Theorem states that no three positive integers a, b, and c satisfy the equation
for any integer value of n strictly greater than two.Let
where n >2Then
must equal:must have opposite remainders for
Adding y to one and minusing y from another will keep them opposite if they are already opposite. So let's see if the two squares have opposite remainders for .
If we add them together they should=0 if they are opposite.
No!
Fermat's Last theorem is True.
#34 Re: Dark Discussions at Cafe Infinity » I am going to climb Everest » 2016-05-10 16:54:43
I don't know, it's just a Maths degree, starting 2017. Doing Foundation Year and Placement Year.
#35 Re: Dark Discussions at Cafe Infinity » I am going to climb Everest » 2016-05-10 05:57:05
Maths now.
#36 Re: Dark Discussions at Cafe Infinity » I am going to climb Everest » 2016-05-09 22:03:57
I got into Uni to do maths! I am going to do that now.
#37 Re: Jokes » Star Wars joke » 2016-05-05 22:11:55
Q: Why did the angry Jedi cross the road?
A: To get to the Dark Side.
#38 Re: Dark Discussions at Cafe Infinity » I am going to climb Everest » 2016-05-05 20:38:17
I am going to do a web design course at college..........don't think I want to go to uni. I have the right mind to make a good programmer because it's based on logic and is creative problem solving.
#40 Re: This is Cool » Using Fermat's Little Theorem to find primes. » 2016-05-03 02:58:24
No way! That's not awesome.
#41 Re: Dark Discussions at Cafe Infinity » I am going to climb Everest » 2016-05-03 02:56:12
Yes. If I don't enjoy it I am just going to quit. But I should enjoy it because it's maths! I already have a philosophy degree but I didn't enjoy it. I think that's how I got my schizophrenia.
#42 Re: Dark Discussions at Cafe Infinity » I am going to climb Everest » 2016-05-03 00:46:58
I have applied to do a math degree! I hope I get in, should do because I am doing a foundation year. Then I can be as clever as you guys!
#43 Re: Dark Discussions at Cafe Infinity » I am going to climb Everest » 2016-05-03 00:15:48
Thirty and counting!
#44 Re: This is Cool » My New Twin Prime Numbers » 2016-05-03 00:03:00
Can be written as....
And we know
So,
569,673=(1x2)+(2x4)+(4x6)+(6x8)+(10x12)+(12x14)+(16x18).
#45 Re: This is Cool » Using Fermat's Little Theorem to find primes. » 2016-05-02 22:33:31
Well usually you'd do
where x=(2-1)(3-1)(5-1)(7-1) and it would be factorable by 2,3,5,7........But if you use a composite Ie. it won't be factorable by 3 and 7.
In this way you can find out if the base is prime or not in one simple calculation!
#46 Re: This is Cool » Using Fermat's Little Theorem to find primes. » 2016-05-02 21:17:44
What if you used the prime as the base? It would be impossible for it to be factorable by factors of a composite because you are minusing 1.
#47 Re: This is Cool » Using Fermat's Little Theorem to find primes. » 2016-05-02 07:34:31
Oh! Fair enough.
#48 This is Cool » Using Fermat's Little Theorem to find primes. » 2016-05-02 06:46:55
- Primenumbers
- Replies: 8
Introduction
The following is a way to find out if (a) is prime or not using Fermat's Little Theorem.
Rule
will be factorable by all primes <square root a if a is prime, otherwise it won't be.x=(All primes below square root a)-1, multiplied together. I.e. (2-1)(3-1)(5-1)(7-1)(11-1)....
a=any odd no.
Theory
Fermat's little theorem states that if p is a prime number, then for any integer a, the number
is an integer multiple of p.So if y=p-1 then will be factorable by p.
We know that remainders repeat themselves in a pattern when multiplying by a. So y could be a multiple of y and the answer would still be factorable by p.
In this way as long as x is factorable by p-1 then the answer will be factorable by p unless (a) itself is factorable by p.
Example
a=37
x=(2-1)(3-1)(5-1)=8
a=21
x=(2-1)(3-1)=2
Conclusion
I don't know but I would have thought this method would be useful for computers as it only requires a few computations. Don't computers usually have to factor possible factors separately? The numbers are very large though.
#49 Re: Dark Discussions at Cafe Infinity » I am going to climb Everest » 2016-04-27 16:47:09
Okay bobbym. I am going to bed now. 6 o'clock in the morning where I am.
Night night.
#50 Re: Dark Discussions at Cafe Infinity » I am going to climb Everest » 2016-04-27 16:39:49
Okay, that's fair.
My avatar is because I used to play judo.
I tend to do everything to the extreme also. My friends used to call me Xtreme when I was a bit younger because I used to do everything to the extreme. Jump off things, drink the most and drive stupidly, stuff like that. I have calmed down a lot now but still enjoy a good challenge! I am at a weird point in my life when I am finally feeling better and I just don't know what to do with myself.