All Questions
56
questions
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) , ...
1
vote
1
answer
92
views
Given a partial prime factorization of $N$ consisting of all primes $p \leq \sqrt{N}$ that divide $N$, how do I find the rest of the factorization?
Given an integer $N$, let $P$ be the set of all primes less than or equal to $\sqrt{N}$ that divide $N$. Define $P_{prod}$ as $\prod_{p \in P} f_N(p)$ where $f_N(p) \gt 1$ is the largest power of $p$ ...
5
votes
3
answers
173
views
Non-squarefree numbers of the form $10^n + 1$
Consider numbers of the form $10^k + 1$. We can look at the prime factorisation of these numbers and note that the smallest such number that has a repeated prime factor is $10^{11} + 1 = 11^2\cdot{}23\...
4
votes
1
answer
120
views
If $p$ can divide $a^n+b^n+c^n$ , can $p^k$ divide it as well?
Related to this
Is there a method to decide whether a given function of the form $f(n)=a^n+b^n+c^n$ ($a,b,c$ fixed positive integers , $n$ running over the positive integers) satisfies the following ...
0
votes
0
answers
146
views
How do we get the number of prime divisors?
We have a natural square-free number $n$ such that $2^5\cdot 3^6\cdot 5^4\equiv 0 \pmod {\tau(n)}$.
Which is the maximum number of different primes that can divide $n$ ?
$$$$
We have that $\tau(n)$ is ...
3
votes
0
answers
92
views
Are there infinite many primes $\ p\ $ that cannot divide $\ 3^n+5^n+7^n\ $?
Let $\ M\ $ be the set of the prime numbers $\ p\ $ such that $\ p\nmid 3^n+5^n+7^n\ $ for every positive integer $\ n\ $ , in short the set of the prime numbers that cannot divide $\ 3^n+5^n+7^n\ $.
...
22
votes
3
answers
695
views
Is $\frac{3^n+5^n+7^n}{15}$ only prime if $n$ is prime?
Let $f(n)=3^n+5^n+7^n$
It is easy to show that $\ 15\mid f(n)\ $ if and only if $\ n\ $ is odd.
I searched for prime numbers of the form $g(n):=\frac{3^n+5^n+7^n}{15}$ with odd $n$ and found the ...
1
vote
0
answers
116
views
How many positive divisors of 7560 are coprime to 15?
I'm trying to find the amount of positive divisors of $7560$ that are coprime to $15$.
I do know how to find the total number of positive divisors a number has but I am not sure how finding those who ...
8
votes
3
answers
505
views
How many numbers are there such that its number of decimal digits equals to the number of its distinct prime factors?
Problem
A positive integer is said to be balanced if the number of its decimal digits equals the number of its distinct prime factors. For instance, $15$ is balanced, while $49$ is not. How many ...
-1
votes
2
answers
50
views
Prove that $a|p+1$ if and only if ${\frac{a}{p} = \frac{1}{n} + \frac{1}{m} }$ such that $n,m \in N$ and $p$ is prime [duplicate]
Let $p$ be a prime and let $n$ be a natural number such that $n \gt a$ .
Prove that $a|p+1$ if and only if exists integers $n,m$
Such that ${\frac{a}{p} = \frac{1}{n} + \frac{1}{m}}$
12
votes
3
answers
462
views
On the diophantine equation $x^{m-1}(x+1)=y^{n-1}(y+1)$ with $x>y$, over integers greater or equal than two
I don't know if the following diophantine equation (problem) is in the literature. We consider the diophantine equation $$x^{m-1}(x+1)=y^{n-1}(y+1)\tag{1}$$ over integers $x\geq 2$ and $y\geq 2$ with $...
0
votes
2
answers
131
views
Proving that $k|(n^k-n)$ for prime $k$ [closed]
Prove that for any integer $n$,we have $(n^k)- n$ is divisible by $k$ for $k=3,5,7,11,13$
I tried using prime factorization but that does not work here
1
vote
2
answers
227
views
Equations involving particular values of the Dedekind psi function and powers of the kernel function
In this post we denote the Dedekind psi function as $\psi(m)$ for integers $m\geq 1$. As reference I add the Wikipedia Dedekind psi function, and [1]. One has the definition $\psi(1)=1$, and that the ...
1
vote
2
answers
226
views
If a prime and its square both divide a number n, prove that $n=a^2 b^3$
Lets call a number $n$ a fortified number if $n>0$ and for every prime number $p$, if $p|n$ then $p^2|n$. Given a fortified number, prove that there exists $a,b$ such that $n=a^2b^3$.
I know that ...
1
vote
4
answers
126
views
$n \in \mathbb{N}$ has at least 73 two-digit divisors. Prove that one of the divisors is 60.
$n \in \mathbb{N}$ has at least 73 two-digit divisors.
I have these questions:
a) How can I prove that one of the two-digit divisors must be number 60?
b) How can I find a natural number that has $\...