All Questions
Tagged with prime-factorization elementary-number-theory
608
questions
3
votes
1
answer
199
views
Smallest "diamond-number" above some power of ten?
Let us call a positive integer $N$ a "diamond-number" if it has the form $p^2q$ with distinct primes $p,q$ with the same number of decimal digits. An example is $N=10^{19}+93815391$. Its ...
- 85.1k
0
votes
0
answers
37
views
Finding square root modulo $n$ and factorization of $n$ [duplicate]
I have this task to prove that the factorization of number $n = p \cdot q$ (where $p$ and $q$ are prime) task is equivalent to finding square root module n.
I have found this lecture that explains the ...
1
vote
2
answers
73
views
Expected number of factors of $LCM(1,…,n)$ (particularly, potentially, when $n=8t$)
I’m trying to prove something regarding $8t$-powersmooth numbers (a $k$-powersmooth number $n$ is one for which all prime powers $p^m$ such that $p^m|n$ are such that $p^m\le k$). Essentially, I have ...
- 1,789
1
vote
1
answer
101
views
distribution of square roots of unity $mod n$ | Factoring with inverse pair
I am writing a proof related to the RSA cryptosystem, specifically showing that given an inverse pair $d, c$ under multiplication mod $\phi(N)$, where
$$ dc \equiv 1 \pmod{\phi(N)}, $$
there exists a ...
- 83
0
votes
0
answers
76
views
Is the following function $f(k)$ surjective?
Let $\omega(n)$ be the number of distinct prime factors of the positive integer $n$.
For a positive integer $k$ , let $s$ be the smallest positive integer such that $\omega(2024^s+k)\ne s$ , in other ...
- 85.1k
2
votes
2
answers
97
views
How to describe integers with the same prime factors?
Is there a term for the relationship between two integers that have the same prime factors? For example, $6=(2)(3)$ and $12=(2)(2)(3)$. Can one describe this with something along the lines of "$...
- 23
26
votes
1
answer
536
views
Prime factor wanted of the huge number $\sum_{j=1}^{10} j!^{j!}$
What is the smallest prime factor of $$\sum_{j=1}^{10} j!^{j!}$$ ?
Trial :
This number has $23\ 804\ 069$ digits , so if it were prime it would be a record prime. I do not think however that this ...
- 85.1k
1
vote
0
answers
68
views
Prime Divisor of the Sum of Two Squares
I'm struggling something immensely to make sense of the following:
https://meiji163.github.io/post/sum-of-squares/#sums-of-two-squares
Factoring an integer in Gaussian integers is closely related to ...
- 2,032
1
vote
1
answer
94
views
Will there be infinity prime numbers of the sort $a^2 -2$ (where $a$ is odd)?
Will there be infinity prime numbers of the sort $a^2 -2$ (where $a$ is odd)?
To begin with, every odd composite number can be written as $a^2$ or as $a_{x}^2 -a_{y}^2$ as long as either $x$ or $y$ ...
- 1,405
3
votes
3
answers
221
views
For what integers $n$ does $\varphi(n)=n-5$?
What I have tried so far: $n$ certainly can't be prime. It also can't be a power of prime as $\varphi(p^k)=p^k-p^{k-1})$ unless it is $25=5^2$. From here on, I am pretty stuck. I tried considering the ...
- 637
2
votes
0
answers
57
views
What did I get wrong in this Mobius function question? [closed]
$f(n):=\sum\limits_{d\mid n}\mu(d)\cdot d^2,$ where $\mu(n)$ is the Möbius function. Compute $f(192).$
First, I found all of the divisors of 192 by trial division by primes in ascending order:
$D=\{...
- 637
4
votes
0
answers
144
views
What are the next primes/semiprimes of the form $\frac{(n-1)^n+1}{n^2}$?
This question is inspired by this question
For an odd positive integer $n$ , define $$f(n):=\frac{(n-1)^n+1}{n^2}$$ as in the linkes question.
For which $n$ is this expression prime , for which $n$ ...
- 85.1k
1
vote
1
answer
84
views
How many different squares are there which are the product of six different integers from 1 to 10 inclusive?
How many different squares are there which are the product of six different integers from 1 to 10 inclusive?
A similar problem, asking how many different squares are there which are the product of six ...
- 45
6
votes
4
answers
1k
views
Fundamental Theorem of Arithmetic - Is my proof right?
My goal was to prove the Fundamental Theorem of Arithmetic without using Euclid's Lemma. There are some proofs online but I haven't found one that uses this idea, so I want to make sure it's right.
...
- 61
0
votes
1
answer
97
views
If $x^2\equiv y^2\mod n$, does $\gcd(x-y,n)$ divide $n$? [duplicate]
If $x^2\equiv y^2\mod n$, does $\gcd(x-y,n)$ divide $n$?
EDIT: I should really be asking if $\gcd(x-y,n)$ is neither $n$ nor $1$, since it will always divide $n$.
I know $n$ must divide $x^2-y^2$, ...
2
votes
1
answer
97
views
Show that $n$ has $2^{\omega(n) - 1}$ coprime factor pairs
I am trying to show that $n$ has $2^{\omega(n) - 1}$ coprime factor pairs. I'm pretty sure this is true but I don't see how to prove it. There is no obvious way to use induction.
Here is an example:
$...
- 3,187
2
votes
1
answer
149
views
Factoring 319375146 without a calculator
The goal is to factor $N = 319375146$ without a calculator, using only pencil and paper in under 30 minutes. The exact question is "What is the 4 digit prime factor of 319375146?" This comes ...
- 5,230
2
votes
0
answers
286
views
Can factoring $90$ help factor $91$?
There are few posts asking if factoring $N-1$ can help factor $N$. In those posts the focus was on the factors of $N-1$ and $N$ which can never be the same. The conclusion therefore was that ...
- 1,058
3
votes
1
answer
217
views
A question about prime factorization of composite Mersenne numbers and $(2^p-2)/(2 \cdot p)$
Mersenne numbers are numbers of the form $2^p-1$ where $p$ is a prime number. Some of them are prime for exemple $2^5-1$ or $2^7-1$ and some of them are composite like $2^{11}-1$ or $2^{23}-1$.
I'm ...
- 141
2
votes
2
answers
262
views
Prime factors of $5^n+6^n+7^n+8^n+9^n+10^n$
I currently run an integer factoring project of the numbers of the form $$5^n+6^n+7^n+8^n+9^n+10^n$$ where $n$ is a non-negative integer.
Do the prime factors have a particular form as it is the case ...
- 85.1k
2
votes
1
answer
98
views
Is $\omega(n)=16$ the maximum?
What is the largest possible value of $\omega(n)$ (the number of distinct prime factors of $n$) , if $n$ is a $30$-digit number containing only zeros and ones in the decimal expansion.
I checked ...
- 85.1k
0
votes
0
answers
59
views
Why trial division algorithm to find the prime factors of $N$ is $O(\sqrt{N})$, even though you need to check after $\sqrt{N}$?
I have understood that to check if $N$ is prime, it is enough to check up to $\sqrt{N}$ because if it has divisor up to that point then it's composite number. However, if you want to count all the ...
- 21
0
votes
3
answers
472
views
Is this algorithm efficient as a factorization algorithm?
Let $N=8*G+3$ $->$ $N=(4*x+2)^2-(2*y-1)^2=p*q$ with $q/p < 2$
Given this system if we choose $D^2$ odd close to $8*x+4$
$->$ $(8*x+4-D^2)=W*V$ with $V$ and $W$ odd very close to each other
...
0
votes
0
answers
31
views
Form of the divisors of a number (Prime Factorization). Is this algorithm-based proof correct? [duplicate]
I am trying to proof the following result:
For a number $n$ whose prime number decomposition is $p_1^{\alpha _1} ... p_m^{\alpha _m}$. Every divisor of $n$ has the form $p_1^{\beta _1} ... p_m^{\beta ...
- 1,231
0
votes
1
answer
59
views
ways to write out a number in exponential form
Let's say that we have a number of the form $n^n$.
How many integer pairs of the form $a^b$ are equivalent to this number?
for example, let's say that $n=8$
We have $2^{24}$, $(-2)^{24}$, $4^{12}$, $(-...
- 362
0
votes
0
answers
71
views
Show for some n Fermat’s method is faster than reverse trial division
One way to find a nontrivial
divisor of n is Fermat’s factorization method:
Suppose that we have an odd number n > 1 which we know is
composite and not a perfect square.
Calculate $\lfloor \sqrt{n}...
- 254
0
votes
0
answers
57
views
Addition on a prime factorization
This question is sort of in-between a computer science question and a math question.
Let's say I'm representing a very large number as a prime factorization in order to not break the limitations of a ...
2
votes
0
answers
56
views
Maximum size of smallest prime factor that has to be expected?
Let $N$ be a positive integer near $$3^{3^{3^3}}$$ Suppose , it has no prime factor below $10^{11}$ as it is the case for $$3^{3^{3^3}}+2^{2^{2^2}}$$
The random variable $X$ denotes the number of ...
- 85.1k
2
votes
0
answers
91
views
Is there any algorithm better than trial division to factor huge numbers?
Suppose , we want to find prime factors of a huge number $N$ , say $N=3^{3^{3^3}}+2$. We can assume that we can find easily $N\mod p$ for some positive integer $p$ (as it is the case in the example) , ...
- 85.1k
4
votes
1
answer
178
views
Is the "reverse" of the $33$ rd Fermat number composite?
If we write down the digits of the $33$ rd Fermat number $$F_{33}=2^{2^{33}}+1$$ in base $10$ in reverse order , the resulting number should , considering its magnitude , be composite.
But can we ...
- 85.1k