Does knowing how $5280$ is a product of primes help you to factor $5281$ as a product of primes?

Question

Does knowing how $5280$ is a product of primes help you to factor $5281$ as a product of primes?

The above question was mentioned in Abstract Algebra book by Gallian.

Prime factorization of

$5280 = 2^5 .3.5.11$

$5281 = 5281$

Answer 1

It does not really help you. Indeed, $5280=2^5\cdot 3\cdot 5\cdot 11$, so that you know that $2,3,5,11$ do not divide $5281$. However, up to the square root you have to test the primes up to $72$ to realize that $5281$ is a prime. In other words, you still have to test division by $$ 7, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71. $$

Edit: The $abc$-conjecture says something on the relationship between the prime decomposition of $a$, $b$ and $c=a+b$. If we have $a+b=c$ in integers, and $a,b$ contain high powers of primes, then $c$ should not do so. For example, $$ 2^{20}+3^{11}=1225723 $$ and $c=1225723$ contains only the first power of a prime. This is consistent with FLT, i.e., that $x^n+y^n$ should not be an $n$-th power $z^n$ for $n>2$.

Answer 2

As in Euclid's proof that there are infinitely many primes, you know that $p_1p_2\dots p_n+1$ is not divisible by any of $p_1,\dots,p_n$.

To check for primality you apparently still need to rule out all of the other possible prime factors, using the Sieve of Eratosthenes, say.

I would say that the answer to Gallian's question is yes. Though you still have a good bit of work left.

Answer 3

If there is suspicion that the number is prime and you have a complete prime factorization of $n-1,$ you may prove primality with the original Lucas primality test. I just programmed it in C++ ; the last line provides a proof that 5281 is prime, as all four powermod numbers are different from $1.$ Note that $-1 \equiv n-1 \pmod n$ is allowed and different from $1,$ we see $5280$ in the successful line.

Wed Sep 30 08:12:52 PDT 2020

5281  n-1:  5280  =   2^5 3 5 11
  2  3  5  11  
   a:  2  q: 2 pmd: 1  q: 3 pmd: 3877  q: 5 pmd: 4166  q: 11 pmd: 845
   a:  3  q: 2 pmd: 1  q: 3 pmd: 3877  q: 5 pmd: 4166  q: 11 pmd: 5156
   a:  4  q: 2 pmd: 1  q: 3 pmd: 1403  q: 5 pmd: 2190  q: 11 pmd: 1090
   a:  5  q: 2 pmd: 1  q: 3 pmd: 1  q: 5 pmd: 1  q: 11 pmd: 1090
   a:  6  q: 2 pmd: 1  q: 3 pmd: 1403  q: 5 pmd: 2190  q: 11 pmd: 5276
   a:  7  q: 2 pmd: 5280  q: 3 pmd: 1403  q: 5 pmd: 2190  q: 11 pmd: 5156

Here is a proof that Dietrich's example 1225723 is prime

n: 1225723    n-1:  1225722  =   2 3 281 727
  2  3  281  727  
   a:  2  q: 2 pmd: 1225722  q: 3 pmd: 1  q: 281 pmd: 736434  q: 727 pmd: 605163
   a:  3  q: 2 pmd: 1225722  q: 3 pmd: 1  q: 281 pmd: 956738  q: 727 pmd: 343840
   a:  4  q: 2 pmd: 1  q: 3 pmd: 1  q: 281 pmd: 412053  q: 727 pmd: 738629
   a:  5  q: 2 pmd: 1225722  q: 3 pmd: 648172  q: 281 pmd: 475560  q: 727 pmd: 983017

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

An example first proved prime by Euler, illustrating the largest idoneal number. Thye output is quite wide, owing to the large numbers and five prime factors.
$$ 197^2 + 1848 \cdot 100^2 = 18518809 $$

 n: 18518809      n-1:  18518808  =   2^3 3 7 11^2 911
  2  3  7  11  911  
   a:  2  q: 2 pmd: 1  q: 3 pmd: 16231349  q: 7 pmd: 16379060  q: 11 pmd: 59331  q: 911 pmd: 3811171
   a:  3  q: 2 pmd: 1  q: 3 pmd: 1  q: 7 pmd: 16379060  q: 11 pmd: 1593851  q: 911 pmd: 2997175
   a:  4  q: 2 pmd: 1  q: 3 pmd: 2287459  q: 7 pmd: 9521077  q: 11 pmd: 1593851  q: 911 pmd: 258990
   a:  5  q: 2 pmd: 1  q: 3 pmd: 1  q: 7 pmd: 11979317  q: 11 pmd: 1  q: 911 pmd: 3946179
   a:  6  q: 2 pmd: 1  q: 3 pmd: 16231349  q: 7 pmd: 9521077  q: 11 pmd: 7734927  q: 911 pmd: 11712163
   a:  7  q: 2 pmd: 1  q: 3 pmd: 1  q: 7 pmd: 6806466  q: 11 pmd: 1593851  q: 911 pmd: 3976121
   a:  8  q: 2 pmd: 1  q: 3 pmd: 1  q: 7 pmd: 11979317  q: 11 pmd: 7734927  q: 911 pmd: 2657590
   a:  9  q: 2 pmd: 1  q: 3 pmd: 1  q: 7 pmd: 9521077  q: 11 pmd: 6348008  q: 911 pmd: 9667332
   a:  10  q: 2 pmd: 1  q: 3 pmd: 16231349  q: 7 pmd: 3830681  q: 11 pmd: 59331  q: 911 pmd: 12244102
   a:  11  q: 2 pmd: 1  q: 3 pmd: 1  q: 7 pmd: 6806466  q: 11 pmd: 1113045  q: 911 pmd: 16378015
   a:  12  q: 2 pmd: 1  q: 3 pmd: 2287459  q: 7 pmd: 11979317  q: 11 pmd: 6348008  q: 911 pmd: 3955206
   a:  13  q: 2 pmd: 1  q: 3 pmd: 2287459  q: 7 pmd: 7039825  q: 11 pmd: 59331  q: 911 pmd: 2226290
   a:  14  q: 2 pmd: 1  q: 3 pmd: 16231349  q: 7 pmd: 7039825  q: 11 pmd: 7734927  q: 911 pmd: 13425126
   a:  15  q: 2 pmd: 1  q: 3 pmd: 1  q: 7 pmd: 3830681  q: 11 pmd: 1593851  q: 911 pmd: 18337913
   a:  16  q: 2 pmd: 1  q: 3 pmd: 16231349  q: 7 pmd: 3830681  q: 11 pmd: 6348008  q: 911 pmd: 693902
   a:  17  q: 2 pmd: 18518808  q: 3 pmd: 2287459  q: 7 pmd: 7039825  q: 11 pmd: 6348008  q: 911 pmd: 14940382

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

https://en.wikipedia.org/wiki/Powerball

https://en.wikipedia.org/wiki/Modular_exponentiation

https://en.wikipedia.org/wiki/Lucas_primality_test

program C++ with GMP... Anything on a line after // is a comment, not affecting the program at all.

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <strstream>
#include <list>
#include <set>
#include <math.h>
#include <iomanip>
#include <string>
#include <algorithm>
#include <iterator>
#include <gmp.h>
#include <gmpxx.h>
#include "form.h"

using namespace std;

//   g++  -o Lucas_Primality Lucas_Primality.cc  -lgmp -lgmpxx
//           set<mpz_class>  div = mp_Divisors( 
//   set<mpz_class>::iterator iter;
//   for(iter = div.begin(); iter != div.end(); ++iter)


// mpz_class  mp_Raise_To_Power( mpz_class  m, mpz_class n)

// set<mpz_class> mp_Prime_Divisors( mpz_class  i)
// mp_powermod( mpz_class  base, mpz_class exp, mpz_class mod)

//   g++  -o Lucas_Primality Lucas_Primality.cc  -lgmp -lgmpxx



int main()
{
  cout << endl; 
  system("date");
  cout << endl;

// ? n = 197^2 + 1848 * 100^2
//  18518809


mpz_class n = 18518809 ;

set<mpz_class> dive = mp_Prime_Divisors(n-1);

   cout << n <<  "  n-1:  " << n-1 <<  "  =  "  << mp_Factored(n-1) << endl;
   set<mpz_class>::iterator iter;
   for(iter = dive.begin(); iter != dive.end(); ++iter)  cout << "  "<< *iter  ;
  cout << "  "  << endl;
   int goon = 1;

  for( mpz_class a = 2; goon && a <= mp_Sqrt(n); ++a)
  {
      if( mp_coprime(a,n)   )
      {
          int goon2 = 1;
          cout <<  "   a:  " << a ;
             for(iter = dive.begin(); iter != dive.end(); ++iter)
             {
                mpz_class q = *iter;
                 mpz_class w = mp_powermod(a, (n-1)/q, n);
                 cout << "  q: " << q << " pmd: "  << w ;
                 goon2 = goon2 & w != 1;
              }  // for iter
           goon = !goon2;
           cout << endl;
      } // coprime
  } // for a



 cout << endl << endl;
 // system("date");
  return 0;
}
 
//   g++  -o Lucas_Primality Lucas_Primality.cc  -lgmp -lgmpxx