Some Factorizations of 2 n ± 1 and Related Results (Q5523028)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3235363
Language Label Description Also known as
default for all languages
No label defined
    English
    Some Factorizations of 2 n ± 1 and Related Results
    scientific article; zbMATH DE number 3235363

      Statements

      Some Factorizations of 2 n ± 1 and Related Results (English)
      0 references
      0 references
      0 references
      1967
      0 references
      factorizations
      0 references
      The authors give a collection of complete factorizations of numbers of the forms: \(2^n\pm 1\), \(2^{2n}\pm 2^n+1\) and \(2^{2n+1}\pm 2^{n+1}+1\) obtained recently an the IBM 7090--94 at the UCLA Computing Facility and the Computer Centre at the University of California, Berkeley. They use the following Theorems of the second author and D. H. Lehmer. Let \(N\) be an odd integer \(> 1\). If \(N-1 =\prod q_i^{\alpha_i}\), \(q_i\) prime and if for each \(q_i\) there exists an \(\alpha_i\) for which \(\alpha_i^{N-1}\equiv 1\pmod N\), but \(\alpha_i^{N-1/q_i}\not\equiv 1\pmod N\), then \(N\) is prime. Let \(U_0=0\), \(U_1=1\), \(U_{n+1} = PU_n-QU_{n-1}\), \(n\geq 1\), \(P\) and \(Q\) integers. If \(U_{n+1}\equiv 0\pmod N\) and if \(U_{m_i}\not\equiv 0\pmod N\), where \(m_i = (N+1)/q_i\) for each prime factor \(q_i\) in \(N+1\), then \(N\) is a prime. They use also other well known tests of primality. They give complete factorizations for the numbers \(2^n-1\) \(\qquad\qquad\) where \(n = 121, 131, 155, 175\); \(2^n+1\) \(\qquad\qquad\) where \(n = 104, 107, 109, 116\); \(2^{2n+1}+2^{n+1}+1\) where \(n = 39, 41, 44, 51, 53, 54, 56, 61, 85\); \(2^{2n+1}-2^{n+1}+1\) where \(n = 44, 47, 48, 53, 55, 58, 61, 62, 63\); \(2^{2n}+ 2^n+1\) \(\qquad\) where \(n = 49, 51, 55, 57, 63, 65, 67, 75, 85, 105\); \(2^{2n}-2^n+1\) \(\qquad\) where \(n = 48, 49, 65, 67\).
      0 references

      Identifiers