# Questions tagged [prime-factorization]

For questions about factoring elements of rings into primes, or about the specific case of factoring natural numbers into primes.

1,599 questions
Filter by
Sorted by
Tagged with
21 views

43 views

76 views

### Probability a natural number of the form $m^2 - n^2$ can be exactly factored as the product of $2$ primes?

Question Let $P$ be the probability that two integers where $m>1$is a fixed positive integer and $n$ is a randomly chosen such than $m> n \geq 0$? What is the probability $m^2 -n^2$ is ...
31 views

### Finding all no-congruent primitive roots $\pmod{29}$

Finding all no-congruent primitive roots $\pmod{29}$. I have found that $2$ is a primitve root $\pmod{29}$ Then I found that is it 12 no-congruent roots, since $\varphi(\varphi(29)) = 12$ Then I ...
34 views

25 views

### Fermat factorization and primality proving

In Fermat factorization you can factor an integer $n$ if you find a nontrivial pair $(x,y)$ such that $x^2\equiv y^2 \mod n$. At the end of the description in https://mathworld.wolfram.com/...
29 views

### Does there always exist a prime $q\equiv3\mod 4$ that divides $p+a^2$ with $p\equiv1$ mod 4

Let $p$ be a prime such that $p\equiv1\mod4$. Is it true that there will always exist a prime $q$ that satisfies $q\vert(p+a^2)$ and $q\equiv3\mod4$, for some integer $a$? I have tried proceeding by ...
38 views

### RSA Number Factorization - question regarding polynomial validity

I am interested in factorizing RSA numbers as a coding challange. I understand the basic principle that $2$ large primes are multiplied together to generate the specific RSA number, however I also see ...
44 views

### Is this a novel factorization theorem? Solving $\sin^2(\pi x)+\sin^2\left(\frac{\pi p}{x}\right)=0$ for $x$ gives the integer factors of $p$.

I have found that $$\sin^2(\pi x) + \sin^2\left(\frac{\pi p}{x}\right)=0$$ solved for $x$ defines the integer factors of $p$. Iteratively applied it also defines the prime numbers smaller than $n$ ...
26 views

I've been thinking about the total number of distinct primes and it occurred to me that for any integers $x > 0, n > 0$, there are at most $n+\pi(n-1)$ distinct primes that divide $\dfrac{(x+n)!}... 2answers 59 views ### Why is$x^{\frac{n-1}{2}}\not \equiv 1 \mod n$If$n=p_1p_2\cdots p_r$and$g_1$is the generator of$U(Z_{p_1})$. Then let$x$be an integer such that$x\equiv 1 \mod p_2p_3\cdots p_r$and$x\equiv g_1\mod p_1$I would like to prove that$x^{\...
55 views

Let $x,n ∈ \mathbb{N}$ such that : $1+x^1+x^2+x^3+\dots +x^{n-1}$ is prime . Proof that $n$ is prime . I actually suppose that $n$ isn't prime absurdly so $n=p×k$ such as $p$ is prime, I also use ...
30 views

38 views

### Is the following an existing conjecture or a conjecture at all?

the following floated to my mind today, can you verify if it stands to be true, or is a pre-existing conjecture. If not, can you correct me? And if it is one, can you prove it? Prime factorisation of ...
46 views

### How to find polynomial $f\in \mathbb{Z}[x]$ with small coefficients, such that $f(m) = 0 \pmod{n})$?

Let $n$ be an integer number, such that $n= p_1 p_2 p_3 \cdots p_k$, where $p_1, p_2, \ldots, p_k$ are not necessarily distinct prime numbers and $k>2$. Also, let $m$ be a given natural number. ...
29 views

### Distribution of composite numbers with $n$ prime factors

Similar to how the Prime Number Theorem approximates the number of primes less than some value $x$, is there a theorem/function that approximates the number of composite numbers with exactly $n$ prime ...
12 views