Half a croissant, on a plate, with a sign in front of it saying '50c'
h a l f b a k e r y
Bone to the bad.

idea: add, search, annotate, link, view, overview, recent, by name, random

meta: news, help, about, links, report a problem

account: browse anonymously, or get an account and write.



Fermat Factoring Factoid

When C is odd, (C mod 4) reveals if m needs to be even or odd, to be greater than n
  [vote for,

It is possible that this Idea is known by many mathematicians, but it is also possible (see 2nd link) that it has previously been overlooked. Since it certainly isn't widely known outside of mathematics, ....

I've described Fermat Factoring in another Idea (first link) so I don't need to repeat it here. What matters here is the result that if C is a composite number, its factors can be described as combinations of two values, m+n and m-n, such that m-squared minus n-squared equals C.

When C is an even number, we all know that one of its factors is 2, which means that either C/2 is another even number (and also divisible by 2) or that C is an odd number (and might be a prime, not a composite number). In this presentation we only want to pay attention to values of C that are both composite and odd.

Now note that if C is a composite odd number, then all its factors must be odd numbers. NOW note that if two of its factors can be described as m+n and m-n, the only way that the results can be odd numbers is if one of the two, m OR n, is an even number, while the other is an odd number. Because of the subtraction, it is normal for m to be assigned the larger of the two values (prevents computing a negative factor of C).

If the factors of C are known, then it is easy to compute m and n. For example, consider 77, which most folks know equals 7*11. To find m, guaranteed to be the larger than n, simply add 7+11 to get 18, and divide by 2 to get 9. m is 9. It is midway between 7 and 11 by a quantity of 2, so n is 2. (And 9-squared minus 2-squared is, indeed, 77.)

For another example, consider 51, which equals 3*17. If we add them to get 20 and divide by 2, then m=10. And since 10 is midway between 3 and 17 by a quantity of 7, n is 7. (And 10- squared minus 7-squared is, indeed, 51.)

Now note that in the first example m is an odd number, while in the second example, m is an even number. This Idea is about, whenever you don't know the factors of C, you can still be certain that m is an even number, OR you can be certain that m is an odd number.

At the 3rd link I have a little table for your edification. It consists of the results of Even Squares minus Odd Squares, the first part of all possible combinations (the RESULTS are listed, not the squares, except for the first column, the result of Zero squared minus odd squares). As you can see, some of the results are negative, simply because sometimes an Even Square is smaller than an Odd Square. If we temporarily ignore the minus signs we can say that all possible values of C-as-odd must be in this table somewhere. (Even primes are in it, having factors of p and 1, which can still lead to computations of m and n.)

But here's the thing: In that table EVERY positive number in the table has the form of 4x+3. And EVERY negative number in the table has the form of 4x+1. The proof that the observation continues for numbers not in the table is simple: If you follow the numbers diagonally from upper-left to lower-right, you can see that the difference between any two numbers is always a multiple of 4. That kind of pattern means that the descriptions 4x+1 and 4x+3 NEVER change. (Also, the differences between adjacent vertical values, and between adjacent horizontal values, are multiples of 4, too. Only when crossing from negative numbers to positive numbers, or vice-versa, do the remainders change, after dividing by 4.)

Anyway, the observation also means that if you divide any odd composite C by 4, and look at the remainder (it will be either 1 or 3), then that can tell you the part of the table where C can be found (the positive numbers or the negative numbers). If the remainder is 1, then C is in the negative part of the table, and if the remainder is 3, then C is in the positive part of the table.

Keeping in mind that the table consists of Even Squares minus Odd Squares, the preceding also tells us that any negative result means that an Odd Square was greater than an Even Square. So when C is shown to be in the negative part of the table, we know that m will be an odd number; if C is shown to be in the positive part of the table, we know that m will be an even number.

Remember we WANT m to be greater than n, so that when n- squared is subtracted from m-squared, the result will be a positive C. And simply dividing C by 4 tells us how to know whether or not m will be even, or odd.

Vernon, Mar 25 2016

Fermat Factoring described (among other things) Factoring_20Algorithm
As mentioned in the main text. [Vernon, Mar 25 2016]

Simple math discoveries are likely still out there http://www.israelha...rticle.php?id=32345
As mentioned in the main text. Note this article describes the theorem poorly; the lines inside the circle all need to be the same length. [Vernon, Mar 25 2016]

Table of Even Squares minus Odd Squares http://www.nemitz.net/vernon/SqrDiffs.png
As mentioned in the main text. The table can fit reasonably well on a piece of "legal" size paper (landscape orientation), if you want to print it out. [Vernon, Mar 25 2016]

Spreadsheet file (LibreOffice) http://www.nemitz.net/vernon/SqrDiffs.ods
The image file was derived from a screen shot of the first spreadsheet; the other two sheets in the file are about studying the diagonals [Vernon, Mar 30 2016]


       There is a more general proof of the factoid of this Idea.   

       Any odd number can be described as having the GENERIC form of either 4x+1 or 4x+3   

       If we multiply 4x+1 by itself, we get
16x^2 + 8x + 1
Since both 16 and 8 are divisible by 4, the net effect is that the square is a number having the GENERIC form of 4y+1 (the fact that y can represent a more complicated expression, such as (4x^2 + 2x), makes no difference when talking about generic stuff).

       If we multiply 4x+3 by itself, we get
16x^2 + 24x + 9
Well! 9=4*2 +1, and that means we could rewrite the overall expression as
4y+1, where y=(4x^2 + 6x +2)
That means the square of ANY odd number has the GENERIC form of 4y+1 (!)

       Therefore we need to see what happens when we subtract 4y+1 from an even square. First, though, we should note that since any even number has a factor of 2, the square of that number will have two factors of 2, which means the square of any even number will be divisible by 4, and thus has the generic form of 4z.   

       If the even square is smaller than the odd square that we want to subtract from the even square, then the Rule For Subtraction is, "subtract the lesser-magnitude value from the greater-magnitude value, and mark the result as negative".   

       So 4z minus a greater-magnitude 4y+1 means we actually do 4y+1 minus 4z, and get -(4(y-z) +1) --and all the negative values in the linked table did indeed each have the generic form of 4-times-something, plus 1   

       If the even square is larger than the odd square, then we need to do a little trick, to prepare for subtraction:
4z equals 4z-4+4 equals 4(z-1) + 4
We can now subtract 4(z-1)+4 minus 4y+1, and get this
4(z-y-1) +3 --and all the positive numbers in the linked table did indeed each have the generic form of 4-times-something, plus 3.
Vernon, Mar 28 2016

       Your excitement makes me wish I understood this better. (+)   

       super nifty [Vernon]   

       I think this could be used as gene logic to figure out things like Did I have sex (even or odd chromosome thing, meiosis, mitosis)   

       also at other technologies I am reminded of fly with wire, or the space shuttle two out of three computers fly the spacecraft. Is it possible there is a super obvious mathematics bettter than of two of three to guide?   

       like you could do mod 4 on computer guided pathwayizing so rather than just knowing it is 2/3 you could know which 2/3 or even notice it was 3/3.   

       from a voltage rather than a digital perspective it would be easy to note three capacitors were together, or three LEDS were modifying a voltage. a mod 4 voltage square wave or ripple could say which 2/3 or say 3/3   

       I thought about a math approach to distributing data at a computer parallel processing computer with n processors. like um, there is a square wave bits (bytes) then if some of these have slightly elevated voltage, the |_|-|_| with the elevated voltage could make it through a capacitor that accumulated a different bnary datastream than the main datastream. the different bnary datastream could be a compressed data thing, then mathematically there is an n, a quantity of rpocessors, where expanding the comrpessed data was actually more efficient than sending the entire decoded data bnary stream along the main datastream. Your modulo 4 even oddness could build that possibly.   

       like um, say you have a a really compressed thing that takes an entire hundredth of a second to decompress. decompressing that at client would be faster than sending it from the opposite side of the earth, rapidifying the internet. kind of like a multivoltage coprocessor could expand an MP$ movie faster than sending it, yet the ultracompressed mp4 would be just slight voltage variations at the data stream that was travelling regardless. so modulo4 to note odd or even could possibly lift out bits to make the compressed data out of.   

       suddenly I conceptualize saying, "photons are different than voltage levels, the internet is photons. hmmm. electrons at microsd cards having multilevel voltage perhaps thus amplifying storage capacity of flash memory to be really ultra high data amounts at a multiprocessor computer possibly...
beanangel, Mar 28 2016

       Your excitement also makes me wish I understood what you said better.   

       "computer guided pathwayizing " [marked-for-tagline]   

       computer guided pathwayizing is um, a way to say computer guided spacecraft trajectory producing as a verb.   

       I think Simple math discoveries are likely still out there is likely   

       I heard about a big bang theory, the thing is I also read that the duodish shape of an erythrocyte actually has higher surface area to volume than a sphere, also the mathematics of that squiggle thing that might be called an antisphere is another continuous lnked curve. the idea that a big bang could be mathematically from something more energy or matter parsimonious than a sphere could be new physics or new math.   

       Also regarding the big bang theory wikipedia says that the blue glow of nuclear reactor comes from cerenkov radiation, which is produced when neutrinos travel faster than light through water or other material with a sufficient refractive index. thus if you think of ultradense matter emitting neutrinos, then the neutrinos actually expand at a radius faser than phtons, so the absorbability of neutrinos at prematter actually effects universe shape as much or more than photon absorption effects of prematter. neutrino shaped universe asymmetry is new to me. yet when you think about the possibility of something more parsimonious than a sphere that would be mathematics that is new to me.
beanangel, Mar 28 2016

       Wait a minute. I thought *everything* had a higher surface-to-volume ratio than a sphere - that a sphere is what you built if you wanted to *minimize* surface area per unit volume. No?
pertinax, Apr 02 2016

       It turns out that a slightly simpler way to identify if m is even or odd is this:
Just add 1 to the odd number c, and divide by 2. If the result is even, then m is even. If the result is odd, then m is odd.

       Note that if c has the form of 4x+3, then adding 1 creates a number having the form of 4x+4, which if divided by 2 yields 2x+2, which *must* be an even number. And if c has the form of 4x+1, then adding 1 creates a number having the form of 4x+2, which when divided by 2 will yield an odd number: 2x+1.   

       Just for fun, consider the composite number c=1155, which is the product of (3)(5)(7)(11). It has all these combinations of pairs of factors:
1 and 1155
3 and 385
5 and 231
7 and 165
11 and 105
15 and 77
21 and 55
33 and 35

       To get m and n (when a pair of factors is known), such that m-squared minus n-squared equals c, the larger number to square (m) is always equal to the sum of a factor- pair divided by 2. And n is simply m minus the smaller factor (OR the larger factor minus m --OR the larger factor minus the smaller factor, which is then divided by two). So:
1 and 1155 yield m=578 and n=577
3 and 385 yield m=194 and n=191
5 and 231 yield m=118 and n=113
7 and 165 yield m=86 and n=79
11 and 105 yield m=58 and n=47
15 and 77 yield m=46 and n=31
21 and 55 yield m=38 and n=17
33 and 35 yield m=34 and n=1

       Feel free to square m and subtract the square of n get 1155 (that is, c) in every case. As guaranteed by the algebra presented at the start of this anno (along with the algebra in the first anno above), since in this example (c+1)/2 yields an even value for m, the larger number to square, ALL the possible values of m are also even numbers.
Vernon, Apr 11 2016


back: main index

business  computer  culture  fashion  food  halfbakery  home  other  product  public  science  sport  vehicle