Questions tagged [prime-factorization]
For questions about factoring elements of rings into primes, or about the specific case of factoring natural numbers into primes.
504
questions with no upvoted or accepted answers
31
votes
0
answers
1k
views
Have I discovered an analytic function allowing quick factorization?
So I have this apparently smooth, parametrized function:
The function has a single parameter $ m $ and approaches infinity at every $x$ that divides $m$.
It is then defined for real $x$ apart from ...
- 1,091
13
votes
0
answers
882
views
Whether there is a prime in sequence $\{1,12,123,1234,12345,123456,1234567,12345678,123456789,12345678910, \cdots\}$
UPD: To make it clearer, here is a statement:
For sequence $A = \{i\in\mathbb{N}_+\mid a_i=a_{i-1}\times 10^{\lfloor(\lg(10n))\rfloor} + n\}$, where $\lg n=\log_{10} n$, show whether there is a prime ...
- 305
11
votes
0
answers
220
views
Prime factors of $\sum_{k=1}^{30}k^{k^k}$
I checked the prime factors of
$$\sum_{k=1}^{30}k^{k^k}$$
and did not find any upto $10^8$
Are there any useful restrictions to accelerate the search ?
- 85.1k
10
votes
1
answer
289
views
$pq\equiv 1\pmod 4$, how to find $p,q\bmod 4$?
Somebody asked me a question, I have no idea about it, the question is:
If a positive integer $n\equiv 1\pmod 4$ is the product of two primes, (denotes $n=pq,$ such as a RSA number) but we don't know ...
- 15.9k
9
votes
0
answers
356
views
When Does $\sigma(q^k)$ Have a Prime Factor Greater Than $q$
Let $q$ be prime and $k$ be a natural number. When does $\sigma(q^k)$ have a prime factor greater than $q$?
We can slightly reduce the problem by noting that
$$\sigma(q^k)=\frac{q^{k+1}-1}{q-1}$$
...
- 5,122
9
votes
1
answer
195
views
Prime Concatenation Order
Consider the following procedure.
Given an integer $n \geq 2$, obtain the canonical prime factorization of $n$, i.e. $\prod_{i=1}^k p_i^{e_i}$. Take the distinct factors $p_i$ and list them in ...
- 219
8
votes
0
answers
120
views
Given the prime factors of two natural numbers, is it possible to decide which of the numbers is greater?
When representing two numbers by their numerals in positional notation, e.g. $720$ and $721$, it is easy to decide which of the numbers is greater by comparing their digits from left to right. ...
- 211
8
votes
0
answers
182
views
Odd numbers with $\varphi(n)/n < 1/2$
The topic was also discussed in this MathOverflow question.
From $\varphi(n)/n = \prod_{p|n}(1-1/p)$ (Euler's product formula) one concludes that even numbers $n$ must have $\varphi(n)/n \leq 1/2$ ...
- 18.2k
8
votes
0
answers
446
views
The Greatest Common Divisor of All Numbers of the Form $n^a-n^b$
For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also ...
- 49.8k
8
votes
0
answers
143
views
Which prime factors of $8^{8^8}+1$ are known?
We have the partial factorization
$$8^{8^8}+1=(2^{2^{24}}+1)\cdot (2^{2^{25}}-2^{2^{24}}+1)$$
The first factor is $F_{24}$. It is composite, but no prime factor is known.
A prime factor of the second ...
- 85.1k
8
votes
0
answers
277
views
How to list the prime factorised natural numbers?
Today I set out to invent a two character numeral system designed to make factorization trivial. Indeed, it lets one factor non-trivial numbers with over thousand digits within 30 seconds per hand - ...
- 12.3k
7
votes
0
answers
174
views
I found a way to calculate Quadratic min mod $N$, but why does it work?
I am trying to factor $N$ using Dixon's factorization method, so I am looking at the equation:
$$a^2\equiv b(\mod{N})$$
If I am able to find $b$ that is a perfect square, I will be able to factor $N$...
- 1,460
7
votes
0
answers
174
views
Fibonaccis and prime numbers
Let $F_n$ denote the $n$th Fibonacci number, and $p_n$ the $n$th prime.
Let $a(n)$ be the smallest positive integer such that $p_n$ is a factor of $F_{a(n)}$.
How can I see that it follows that ...
7
votes
0
answers
93
views
Prove there are infinitely many integer solutions to $z^z = y^y x^x$ for with $x,y,z > 1$
I have tried a number of methods using prime factorisations but they inevitably lead to invoking too many unknowns for me and balloon in complexity.
- 624
6
votes
0
answers
100
views
Factorizations not sharing digits with original number
The sequence A371862 is "Positive integers that can be written as the product of two or more other integers, none of which uses any of the digits in the number itself."
In the extended ...
- 21.4k