All Questions
Tagged with prime-factorization elementary-number-theory
608
questions
3
votes
1
answer
178
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
71
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
99
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
531
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
67
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,022
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,415
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
56
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
83
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
96
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$, ...
