Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [prime-factorization]

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

7
votes
1answer
84 views

How can I speed up the search for a special number?

A number $N$ is given. The object is to find the smallest nonnegative integer $k$, such that $N+k$ is the product of three distinct primes, each having the same number of decimal digits. For example,...
0
votes
1answer
55 views

The prime factorization of $15$ when finding the number of solutions to $15=a^{2}+b^{2}$.

Find the number of solutions to $15=a^{2}+b^{2}$. My professor told us to write $15$ in the form $2^{a}p_{1}^{t_{1}}\cdots p_{n}^{t_{n}}q_{1}^{c_{1}}\cdots q_{m}^{c_{m}}$, and if any $t_{i}$ is odd, ...
0
votes
3answers
65 views

Find a prime divisor of the these numbers

Find a prime divisor of a) $2^{49} + 1$ b) $50^{125}-1$ c) $2^{49} -1$ d) $2^{52} +1$ Note that $2^m+1$ is not prime unless $m=2^k$, $2^m-1$ is not a prime unless m is ...
5
votes
1answer
96 views

What other uses are there for Prime numbers?

Simple question out of curiosity... Beside the use of cryptographic safety and prime factorization, what other uses are there for prime numbers? Thank you. Edit: To clarify and not confusing with ...
1
vote
0answers
22 views

Non-Linear Diophantine Equation in Two Variables [duplicate]

How many solutions are there in $\mathbb{N}\times \mathbb{N}$ to the equation $\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{1995}$ ? I could solve till I got to the point where $1995^2$ is equal to the ...
5
votes
1answer
68 views

Is the palindrome-prime factor of $p-1$ always larger than that of $p+1$?

Suppose, $p\ge 7$ is a palindrome-prime , the largest prime factor of $p-1$ is a palindrome-prime and the largest prime factor of $p+1$ is also a palindrome-prime. Must the prime factor of $p-1$ ...
0
votes
0answers
15 views

Does the probability , that an ellitpic curve finds a factor, heavily depend on the factor?

The elliptic curve method is an efficient method to find small prime factors of arbitary large numbers. It generalizes the $p-1$-method. The table for the elliptic curve method reveals that, for ...
1
vote
1answer
40 views

Which is the smallest semiprime above $10^k$ with the desired property?

Let $k\ge 3$ be an intger. The object is to find the smallest number $n$ above $10^k$ which is the product of two distinct primes, each greater than $11$ and containing at most $2$ distinct decimal ...
0
votes
0answers
14 views

Prove that if $a$ and $b$ are coprime and the product $ab$ is some $m$-th power ($m\ge2$), then $a$ and $b$ have to be $m$-th powers. [duplicate]

i.e $ab=c^m$ for some $c\in\mathbb{Z}$, $m\in\mathbb{N}$. So far I have Let $p_1,\dots,p_n,q_1,\dots, q_k$ be primes $$a=p_1^{x_1}\cdot p_2^{x_2}\cdot ... \cdot p_n^{x_n}$$ $$b=q_1^{y_1}\cdot ...
0
votes
1answer
45 views

Prime factor of larger numbers by hand/simple calculator $12402^5$

Trying to work out a prime number factorization (preparing myself for an upcoming exam). We have worked a bit with prime number factorization and $\gcd$ during this semester. I know how to approach ...
1
vote
1answer
74 views

Prove that $8p^2+2p+1$ is prime number [duplicate]

If $p$ and $8p^2+1$ is prime number than $$8p^2+2p+1$$ is prime number proof. I know that prime number can write as a multiply 1 and $8p^2+2p+1$, so if I show that this number is a multiply $a*b$ ...
5
votes
0answers
74 views

Expected number of digits of the smallest prime factor of $77^{77}-18$

Let $X$ be the number of digits of the smallest prime factor of $$77^{77}-18$$ which is a composite $146$-digit number. ECM indicates that the smallest factor has more than $30$ digits. Assuming ...
8
votes
1answer
341 views

A conjecture on consecutive odd composite numbers

Can you provide a proof or a counterexample for the claim given below? Inspired by Grimm's conjecture I have formulated the following claim: Let $n_1,n_2,\dots,n_k$ be a sequence of $k$ ...
1
vote
1answer
40 views

A strange seemly pattern from some even numbers. Is there a known theorem that can explain this pattern?

So when arguably having a lot of free time and try to enumerate the prime factorisation of the numbers 0-100 \begin{align} & 0\\ & 10\\ & 01\\ & 0010\\ & 020\\ & 00010\\ ...
0
votes
1answer
19 views

Base $b$ and efficient integer factorisation

I was just looking at the RSA encryption Wikipedia page. RSA encryption essentially boils down to our inability to factorise huge semi-primes. But then I had the idea of converting the number to base ...
1
vote
0answers
65 views

What are the most (and least) likely factors of a composite Mersenne number?

What are the most (and least) likely factors of a composite Mersenne number? Suppose some number $M_p=2^p-1:p\in\text{prime}$ is a candidate for a Lucas Lehmer test. Is it possible to identify a set ...
1
vote
1answer
48 views

Ring with infinitely reducible elements

Can you give or construct an elementary example of a factorial ring with elements which are product of infinitely many irreducible elements? i.e. there are reducible elements that can't be written as ...
0
votes
1answer
18 views

Prime Factorization of very large integer with quadratic residue and its square roots

We have a very large modulus integer n also we have very large number y we know that y is a quadratic residue modulus n.Also we know all 4 square roots of y. What is the best way of prime ...
1
vote
2answers
41 views

What is the least prime factor of $n^i \cdot m^j$, for prime numbers $n, m$ such that $n < m$?

The least prime factor (lpf) of a natural number is the smallest prime number that divides that number. In particular the least prime factor of any even number equals $2$ and the least prime factor of ...
1
vote
1answer
37 views

How does this method work to find prime numbers?

I'm curious about this pattern that I saw while adding many powers of two together, and then taking the prime factorisation of each result, and I'm curious as to why this occurs. Here is the pattern: ...
6
votes
1answer
92 views

Prime divisor in positive integers sequences

I would like to know if anyone has an ideea if the following statement is true. For any sequence of consecutive positive integerers $(n_0, n_0+1,..., n_0+k).$ Where $n_0 \ge 1, k\ge 0,$ but $k\ge 1$ ...
1
vote
0answers
47 views

Generating prime factors of a certain congruence?

I'm aware that prime factors of $n^2+1$ take the form $4k+1$. It's also well known that factors dividing $\frac{a^p \pm 1}{a \pm 1}$ will be congruent to $2kp+1$. Fibonacci and some other recurrence ...
1
vote
2answers
52 views

Question E4.2- Probability with Martingales by Williams

For $s > 1$, define the zeta function as $$\zeta(s):= \sum_{n=1}^{\infty} \frac{1}{n^s}.$$ Given a probability space $(\Omega,F,P)$, let $X : \Omega \rightarrow {1,2,3,\ldots}$ and $Y : \...
4
votes
3answers
167 views

Divisors of $\left(p^2+1\right)^2$ congruent to $1 \bmod p$, where $p$ is prime

Let $p>3$ be a prime number. How to prove that $\left(p^2+1\right)^2$ has no divisors congruent to $1 \bmod p$, except the trivial ones $1$, $p^2+1$, and $\left(p^2+1\right)^2$? When $p=3$, you ...
0
votes
0answers
33 views

General formula for the probability to find a factor in the elliptic curve method?

I am aware of tables showing the optimal $B1$ and the probabilities for some values. But I would like to know the general approach to get the probabilities. Suppose, a given factor with $n$ digits ...
0
votes
1answer
57 views

Proof for relation between p-adic valution of the total number of divisors and the sum of multiplicities

The final point $(9)$ is the lemma that I am establishing a proof for, all the relevant lemma are there I guess I just need help fine tuning things, Although I have no idea how I will prove $(10)$ if ...
5
votes
1answer
203 views

Factorization of a $116$-digit number

What is the prime factorization of this number : $$2510840694154672305534315769283066566440942177785613805158$$ $$3255420347077336152767157884641533283220471088892806902579$$ ? If we concatenate the ...
1
vote
1answer
89 views

Targeting all prime numbers with a minimal set of sinusoidal functions

Given the series of prime numbers greater than 9, we can organize them in four rows, according to their last digit ($d=1,3,7$ or $9$), and in $k=1,2,3\ldots$ columns corresponding to the $k$-multiple ...
0
votes
1answer
31 views

Suppose a prime number $p$ divides the product $a_1 a_2 … a_n \in \mathbb{Z} $ then $p$ divides at least one of the factors of $a_i$

I know i need to use induction but i really have no concept on how to go about it. Base case: Let $p$ divide $a_1$ then p will be a factor of $a_1$??? Inductive step: No idea how to phrase this.
0
votes
1answer
48 views

Find X in the Equation

Im not a mathematician and I have forgotten about some basics in mathematics. I have this equation: (x^y) mod z = w Given y, z and w, how will I find x? How ...
2
votes
2answers
62 views

Basics of Quadratic Sieve algorithm

I'm trying to understand Quadratic Sieve algorithm for integer factorization, I follow the description in the book "Prime Numbers" by Crandall and Pomerance, specifically the Algorithm 6.1.1. (Even ...
2
votes
1answer
26 views

Stage 1 of Elliptic Curve Method (ECM)

Reading several texts of ECM (e.g. 20 years of ECM) the Stage 1 is described as: $Q \leftarrow P_0$ for each prime $\pi <= B_1$ $\quad$compute $k$ such that $\pi^k <= B_1 < \pi^{k+1}$ $\quad$...
1
vote
1answer
108 views

Given $\varphi (n)$ and $n$ for large values, can we know prime factors of $n$

If a number is product of two primes, then given its totient function, we can know its prime factors, but how do we do this in generic case? If the number could have more than two prime factors can ...
3
votes
0answers
46 views

Factorising a divisor of a product

In the ring of integers (or the monoid of natural numbers under multiplication), I believe that the following theorem holds: Lemma Set $m$, $a$, $b$. If $m | ab$ then there exist $u$, $v$ such that $...
2
votes
1answer
62 views

Semiprime factorization

I was thinking about semiprime factorization, and I had an idea of an algorithm: Let's take a small semiprime for this example: 3053. So we have to primes ...
0
votes
0answers
28 views

Prime factorization formalism

I was hoping someone might know the name for this representation of the positive integers. The idea is similar to Peano's arithmetic but applied to multiplication. So we have 1, multiplication and a ...
2
votes
0answers
34 views

How many set of size $m$ integers such that the product is $n$

just a small combinatoric question related to optimizing the amount of computations of a program (for some reasons). How many sets of $m$ naturals can be formed such that their product equals the ...
1
vote
0answers
44 views

Fermat Kraitchik Factorization Method

I am struggling to understand the following passage from my number theory book, i'm not sure i like his choice of language however it is the only book i can get a copy of for now. That being said I ...
0
votes
0answers
56 views

Finding the smallest prime factor of $\sum_{a=1}^N a^{k}$

It is linked to my previous question, but I wanted a ++ clear explanation: Suppose we have a huge number of that type with a huge $k$. $\sum_{a=1}^N a^{k} =1^{k}+2^{k}+3^{k}+...+N^{k}$ And we want ...
0
votes
1answer
63 views

Find the smallest positive prime divisor of …

Problem: That's a problem I have found on the web. I didn't understand the solution: Why?? Given solution: How all this sequence has been transformed into $$33-{\lfloor {33\over p}\...
5
votes
2answers
80 views

What is the multiplicative order of a product of two integers $\mod n$?

Standard texts prove that $\textrm{ord}_n(ab)=\textrm{ord}_n(a)\,\textrm{ord}_n(b)$ when $\textrm{gcd}(\textrm{ord}_n(a),\textrm{ord}_n(b))=1$. What if they are not relatively prime? Here $\textrm{...
10
votes
1answer
170 views

Prime divisors of the sequence terms $a_n=a\cdot 2017^n+b\cdot 2016^n$

I am dealing with the test of the OBM (Brasilian Math Olimpyad), University level, 2017, phase 2. As I've said at another topic (question 1), I hope someone can help me to discuss this test. The ...
3
votes
2answers
34 views

Find the prime factorisation of $6500$ and $1120$, and write down, in factorised form, $\gcd(6500, 1120)$ and $\operatorname{lcm}(6500, 1120)$.

(i) Find the prime factorisation of $6500$, and of $1120$. What is the typical way to go about this? Just using common divisibility rules? That's what I did. I'm not sure if there's a more structured ...
3
votes
1answer
51 views

Why a certain integral domain is not a UFD.

Let $$\mathbb{Z}[q]^{\mathbb{N}} = \varprojlim_j \mathbb{Z}[q]/((1-q)\cdots (1- q^j))$$ Why isn't $\mathbb{Z}[q]^{\mathbb{N}}$ a unique factorization domain? The author proposes a proof whose ...
1
vote
1answer
65 views

Product of a known prime

Lets say we have a set of numbers k = [44, 3, 17, 10, 64] and a known prime number p=11. How do I filter all the numbers from ...
8
votes
4answers
118 views

Determining Whether the Number $11111$ is Prime. Used Divisibility Tests.

I am asked to determine whether the number $11111$ is prime. Upon using the divisibility tests for the numbers 1 to 11, I couldn't find anything that divides it, so I assumed that it is prime. However,...
0
votes
0answers
38 views

Find the cardinality of the set $A_p$ defined as the following : [duplicate]

For any prime number $p$, $A_p$=the set of integers $d\in \{1,2,3,\dots, n\}$ such that the power of $p$ in the prime factorization of $d$ is odd. Then \begin{align*} A_p= & \lfloor\dfrac{n}{p}\...
1
vote
1answer
39 views

finding the number of positive divisors for a 1111…1 1992 times

So the actual question is to prove that the number of positive divisors is even. But to do that I have to find the number of positive divisors for 111.....1(1992 1's). I know that I should try to find ...
3
votes
1answer
118 views

Find the largest of the three prime divisors of the number $13^4 + 16^5 - 172^2$

I was able to factor out only the prime 13,thus $13^4 + 16^5 - 172^2=13\cdot 80581$ What should be done to solve it? (Maybe some clever factorization, modulo, or anything else?)
2
votes
3answers
80 views

If $S(n)$ is an odd integer, what is the sum of all possible $\frac1n?$ [closed]

If $n$ is a positive integer, let $S(n)$ be the sum of all the positive divisors of $n$. If $S(n)$ is an odd integer, what is the sum of all possible $\frac1n?$ The function $S$ is multiplicative ...