Questions tagged [prime-factorization]
For questions about factoring elements of rings into primes, or about the specific case of factoring natural numbers into primes.
2,081
questions
-2
votes
1
answer
131
views
A positive integer is called ”nice” if it has at least three distinct positive divisors. How many ”nice” integers are there less than 100?
Well I've tried counting
p^2 <= 100 (where p is a prime) there are 4 such no.s
{4, 9, 25, 49} which have exactly 3 distinct divisors but how'd I be covering all cases less than 100
Thank You
1
vote
1
answer
67
views
What do the products in a modulus in Class Field Theory mean?
I am reading Cox's Primes of the form $x^2+ny^2$. There, he's given the following definition:
Given a number field $K$, a modulus in $K$ is a formal product $$\mathfrak{m}=\prod_{\mathfrak{p}}\...
- 600
0
votes
2
answers
156
views
What is the number of digits of the smallest number $n$, such that $20\mid n$ and $n^2$ is a perfect cube, $n^3$ is a perfect square?
Let $n$ be the smallest positive integer such that n is divisible by $20$, $n^2$ is a perfect cube, and $n^3$ is a perfect square. What is the number of digits of $n$ ?
How to express in algebra $n=2^...
user1202341
1
vote
1
answer
183
views
Infinite primes in number fields
David Cox's Primes of the form $x^2+ny^2$ defines infinite primes as
[Infinite primes] are determined by the embeddings of $K$ into $\mathbb{C}$. A real infinite prime is an embedding $\sigma: K \to \...
- 600
2
votes
1
answer
102
views
Ratio between largest and smallest prime factor
For a Carmichael-number $N$ let $p$ be the smallest and $q$ the largest prime factor. Consider $r:=\frac{q}{p}$. We could call a Carmichael "balanced" , if $r\approx 1$ , say $r<1.1$.
...
- 85.1k
2
votes
0
answers
50
views
The number of integers less than x that have at least two distinct prime factors of bit size greater than one-third the bit size of x
Sander came out with a paper describing how to generate what he calls an RSA-UFO. Anoncoin then utilizes this and mentions that the paper proves that the probability that a randomly generated integer, ...
- 123
0
votes
2
answers
101
views
pythagorean triple factorization
Let $z>y>x$ primitive pythagorean triple.
Show that $z$ has a prime factorization to primes of the form $4k+1$
I tried using the fact that there exist $s,t$ such that $s$ is not congruent to $t$ ...
- 211
1
vote
1
answer
157
views
Is it correct to say that prime numbers don't exist on $\mathbb{R}$ and $\mathbb{Q}$?
A prime number is defined as: "A non invertible and non zero numer $p$ of a ring $A$ is called a prime number if any time it divides a product of two numbers, it also divides one of the factors&...
- 121
1
vote
1
answer
79
views
Continued aliquot sums
What happens if one takes the aliquot sum of an integer and then repeats the process so that one takes the aliquot sum of all of those factors that were not reduced to the number 1 on the previous ...
5
votes
1
answer
123
views
Are there infinite many primes that cannot be the largest prime factor of a Carmichael-number?
Let $S$ be the set of prime numbers $p$ that cannot be the LARGEST prime factor of a Carmichael-number.
The first elements of $S$ are : $$[2, 3, 5, 7, 11, 13, 23, 43, 47, 53, 59, 83]$$
Does $S$ ...
- 85.1k
2
votes
0
answers
127
views
Smallest prime factor of $F_{F_{38}}+F_{38}+1$ wanted
This question is related to this one.
Let $F_n$ be the $n$-th fibonacci number and $p(n)$ be the smallest prime factor of $$f(n):=F_{F_n}+F_n+1$$
The values $p(n)$ except for $n=11$ and $n=38$ upto $n=...
- 85.1k
1
vote
2
answers
69
views
Factorization over $\mathbb{Q}$ and $\mathbb{Z_{41}}$
Factor $f(x) = x^4+1$ over $\mathbb{Q}$ and over $\mathbb{Z_{41}}$.
1)I can't factor $f(x)$ over $\mathbb{Q}$ because $f(x+1)$ is irreducible by Eisenstein's criterion.
2)I don't know where to start:
...
- 45
2
votes
0
answers
66
views
Can $F_n+n$ have arbitary many distinct prime factors?
For a positive integer , define $$f(n):=\omega(F_n+n)$$ where $F_n$ denotes the $n$-th fibonacci-number and $\omega(n)$ denotes the number of distinct prime factors of $n$.
Define $g(k)$ as the ...
- 85.1k
2
votes
1
answer
86
views
Show that for an odd integer $n ≥ 5$, $5^{n-1}\binom{n}{0}-5^{n-2}\binom{n}{1}+…+\binom{n}{n-1}$ is not a prime number.
I would prefer no total solutions and just a hint as to whether or not I’m at a dead end with my solution method.
So far this is my work:
From the binomial expansion,
$$\sum_{j=0}^n 5^{n-j}(-1)^j\...
- 183
0
votes
0
answers
67
views
Have numbers of this form forced small factors?
Let $F_n$ be the $n$ th Fibonacci-number and define $$f(n):=F_{n^2}-F_n+1$$
For most integers $n>1$ , $f(n)$ has a small prime factor :
...
- 85.1k
0
votes
1
answer
140
views
How to factor numbers like 8,023 manually
I was given a random 4-digit number to factor over the prime numbers. My number was 8,023. I tried applying all the divisibility rules up to 36 before giving up on them. I tried using algebra as ...
- 2,370
1
vote
1
answer
61
views
How would one show that any given prime p_i must be a factor of some (p_j - 1)? Is that a true property of primes even? [closed]
In short, what I'm asking is, if you were to go through the whole set of positive primes term by term and find for each prime p the prime factorization of (p - 1), whether all prime numbers would ...
- 19
0
votes
1
answer
71
views
Calculating factorization for large numbers
My mission is to calculate the factorization of large numbers, for example, from $start=1e11$ to $end=1e12$.
To do that, one approach that I was thinking of is to calculate for each number his ...
- 119
-1
votes
2
answers
111
views
Prime and Integer Factorization
Often in problems I find myself having a hard time factoring really large or "complex" numbers.
How am I supposed to know that $43,911$ is $41 * 63 *17$ ?
Are there any methods or tricks or ...
- 109
1
vote
0
answers
86
views
Efficient algorithm for finding the number within an interval given its prime factors
Suppose we are given two integers $\ell$ and $h$ such that $\ell \leq h$ and a list of distinct prime numbers $P = [p_1,p_2,\dots,p_n]$ (sorted in ascending order). We are interested in finding an ...
- 201
2
votes
0
answers
173
views
Question about the collection of the prime factors of a fibonacci number
A positive integer $n$ is called pandigital , if every digit from $0$ to $9$ occurs in the decimal expansion of $n$.
Conjecture : The largest non-pandigital fibonacci-number (a fibonacci-number with ...
- 85.1k
1
vote
1
answer
104
views
Finding the (smallest) next number with the same distinct prime factors as a previous number
(Since there is no answer yet, I removed most "EDIT"'s to make the text more readable)
Today, I was trying to find a natural number $n_{2}$ such that this number has the same distinct prime ...
user1114342
2
votes
0
answers
101
views
What are nontrivial factors of $F_{F_n}$ upto $n=137$?
Let $F_n$ denote the $n$ th Fibonacci number and define $f(n):=F_{F_n}$
$f(n)$ is prime for $n=4,5,7$
If we have $n>4$ and $F_n$ is composite , then we only have to know a prime factor of $F_n$ , ...
- 85.1k
-2
votes
1
answer
109
views
A number theory problem I saw, related to prime factors [closed]
Prove that there are infinitely many prime factors of numbers of the form $2^{3^k}+1$.
- 476
1
vote
1
answer
77
views
Legendre's Conjecture and estimating the minimum count of least prime factors in a range of consecutive integers
I recently asked a question on MathOverflow that got me thinking about Legendre's Conjecture.
Consider a range of consecutive integers defined by $R(x+1,x+n) = x+1, x+2, x+3, \dots, x+n$ with $C(x+1,x+...
- 10.5k
1
vote
0
answers
93
views
What is the name of a number that does not have repeating prime factor
For example, $10$ does not have repeating prime factor, $2$ and $5$, while $20$ have repeating prime factor, $2 \cdot 2 \cdot 5$. What is the name of number that does not have repeating prime factor? ...
- 113
2
votes
2
answers
127
views
The equation $175a + 11ab + bc = abc$ [closed]
Consider all the triples $(a, b, c)$ of prime numbers that satisfy the equation
$$175a + 11ab + bc = abc\ .$$
Compute the sum of all possible values of $c$ in such triples.
I could only get to the ...
- 33
0
votes
0
answers
42
views
About the proof of reduction of factoring to order finding
Inside the book I'm following there's a theorem, used to prove the factoring algorithm, which states:
Suppose $N = p_{1}^{\alpha_1}p_{2}^{\alpha_2}\dots p_{m}^{\alpha_m}$ is the prime factorization of ...
0
votes
2
answers
614
views
Method to finding the number of factors [duplicate]
I've seen that the number of factors of $x$ can be found:
Prime factorising $x$
Taking each power in the factorisation and adding $1$
Multiplying these numbers together.
This results in the number ...
- 855
3
votes
2
answers
275
views
Is there an efficient algorithm for generating all numbers with n distinct prime factors in order?
Bit of an x y problem here, so in full disclosure, I am attempting to find the next term of A152617, "Smallest number m such that m has exactly n distinct prime factors and sigma(m) has exactly n ...
- 270