Re: Factoring


"Mirror" <andxfiles@xxxxxxxxxx> wrote in message
news:8g3p43phdo0sufa7hti0i7lks4kf40ckcm@xxxxxxxxxx
On Thu, 17 May 2007 18:08:26 +0100, "Nick" <tulse04-news1@xxxxxxxxxxx>
wrote:


"Mirror" <andxfiles@xxxxxxxxx> wrote in message
news:1179416286.828485.126030@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I have made an observation about prime numbers.

All prime numbers - except 2 and 5 - have as their last digit, either
1 or 3 or 7 or 9. ( it can't be 5 because it would then be divisable
by 5 ).

We notice that the last digit of the multiplication of two prime
numbers ( except the trivials 2 and 5 ) is also 1,3,7 or 9. How is
that ?

It can't be 5 because as you have rightly pointed out, it would be
divisible
by 5. And two odd numbers multiplied together must be odd.

let's take the last digits combinations as they are produced from the
multiplication algorithm :

1x1=1
1x3=3
1x7=7
1x9=9
3x3=9
3x7=21->1
3x9=27->7
7x7=49->9
7x9=63->3
9x9=81->1

So for each number of the form P*Q where P and Q are primes, we know
with big accuracy what is the last digit of the 2 primes P and Q.

The possible combinations for each possibility of last digit are :

number's last digit 1, possible combinations of primes' last digits :

1 and 1
or
3 and 7
or
9 and 9

number's last digit 3, possible combinations of primes' last digits :

1 and 3
or
7 and 9

number's last digit 7, possible combinations of primes' last digits :

1 and 7
or
3 and 9

number's last digit 9, possible combinations of primes' last digits :

1 and 9
or
3 and 3
or
7 and 7

as an example let's the number 38293 ( which is 149*257 ). Its last
digit is 3, so the possible combinations for the last digits of the
primes ( which we don't know ) are :

1 and 3
or
7 and 9

this fact can possibly lead to a factorization in polynomial time or
even faster.

I think that we are probably fairly familiar with the grid of numbers that
forms a prime number ie that they are odd apart from 2 and it can't be 5.
Then this excludes every one that is divisible by every other preceding
odd
number.

Where is this going?

Nick

it goes to that we can tell with big accuracy which are the last
digits of the two primes, and was thinking if we could - in a reverse
way - retrieve the rest of the digits

Prime => the last digit is 1, 3, 7 or 9, but not the other way around, and
it is fairly obvious.

But you didn't imply (pace Mensanator) that 9 was prime.

Nick


.

Relevant Pages

  • Re: My vbScript answer to the Google Question. {the first 10 digit prime in e}.com
    ... 10 digit numbers are not very big. ... primes is faster than my method of using Eratosthenes sieve to ... precalculate the actual primes. ... I keep getting a type mismatch error on this line: ...
    (microsoft.public.scripting.vbscript)
  • Re: Primes in DNA (was: Definition Challenge)
    ... digit length in DNA found in earthly species. ... First twenty primes in binary: ... excluded from the last digit position forever and ever! ... there is no such list of quaternary primes in the genome ...
    (talk.origins)
  • Re: Factoring
    ... We notice that the last digit of the multiplication of two prime ... And two odd numbers multiplied together must be odd. ... So for each number of the form P*Q where P and Q are primes, ... Then this excludes every one that is divisible by every other preceding odd ...
    (sci.math)
  • Evidence For The Randomness Of Prime Numbers
    ... randomness of prime numbers based on the Last Digit Distribution. ... Aside from 2 and 5 there are no even primes or primes ending in the ... the last digit distribution as expressed by the Chi-square. ...
    (sci.math)
  • Re: Factoring
    ... We notice that the last digit of the multiplication of two prime ... And two odd numbers multiplied together must be odd. ... So for each number of the form P*Q where P and Q are primes, ... Then this excludes every one that is divisible by every other preceding odd ...
    (sci.math)