All Questions
Tagged with prime-factorization divisibility
130
questions
4
votes
0
answers
99
views
Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is divisible by at least one prime number less than $n$
As a continuation of this question relating the Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is composite and this other one on the divisibility of numbers in intervals ...
- 1,190
3
votes
1
answer
58
views
Divisibility of numbers in intervals of the form $[kn,(k+1)n]$ [duplicate]
I have checked that the following conjecture seems to be true:
There exists no interval of the form $[kn, (k+1)n]$ where each of the integers of the interval is divisible by at least one of the ...
- 1,190
6
votes
1
answer
134
views
Conjecture: $\prod\limits_{k=0}^{n}\binom{2n}{k}$ is divisible by $\prod\limits_{k=0}^n\binom{2k}{k}$ only if $n=1,2,5$.
The diagram shows Pascal's triangle down to row $10$.
I noticed that the product of the blue numbers is divisible by the product of the orange numbers. That is (including the bottom centre number $...
- 25.8k
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
1
vote
1
answer
179
views
How to get the smallest $n$ that $n^n$ is divisible by $m$.
I have to calculate an integer $n$ when an integer $m$ is given, that $n^n$ is divisible by $m$.
And the thing is, $n$ is the smallest number that satisfies this condition.
Please help me how can I ...
- 11
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$ ...
- 1,497
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\...
- 355
1
vote
0
answers
61
views
Subset of natural numbers with largest amount of divisors
Let $n, k \in \mathbb{N}$, with $k \le n$.
Which $k$ natural numbers not greater than $n$ have the largest amount of divisors altogether?
Formally, let $D(x)$ be the set of positive divisors of some $...
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 ...
- 85.1k
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 ...
- 14k
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\ $.
...
- 85.1k
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 ...
- 85.1k
-1
votes
2
answers
124
views
How to understand special prime factorization method
Normally when we want to find the Prime Factorization of a number, we will keep dividing that number by the smallest prime number (2), until it can't be divided then we move on to the next prime ...
0
votes
2
answers
122
views
Divisibility property involving binomial coefficients and largest prime power divisor [duplicate]
Let $p$ be a prime, let $x$ be an integer not divisible by $p$, and let $j\geq 1$. Denote, as usual, by $\nu=\nu_p(j+1)$ the largest exponent such that $p^{\nu}$ divides $j+1$.
My question : is it ...
- 61.7k
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 ...
- 11
0
votes
0
answers
30
views
Why for every range of N numbers, there are always approximately 0.392*N numbers which contains perfect squares as factors? [duplicate]
As to my current understanding, when simplifying radicands of roots what we are really doing is checking if this said number contains a perfect square number as a factor. Studying the distribution of ...
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 ...
- 3,966
-1
votes
2
answers
499
views
Let $n$ be a positive integer relatively prime with $10$. Prove that the digits of hundreds of $n^{20}$ is even. [closed]
Let $n$ be a positive integer relatively prime with $10$. Prove that the hundreds digit of $n^{20}$ is even.
I know this has something to do with $\bmod 1000$, I'm just not sure how to write a proof ...
2
votes
1
answer
59
views
How to find the number of compound divisors of the smallest product from two unknown numbers?
The problem is as follows:
The number of panadol pills at a pharmacy is a positive whole number
that it has two prime divisors and 45 positive divisors. The number of
tylenol pills at the same ...
- 4,185
1
vote
1
answer
57
views
When is the number of Divisors of a Number equivalent to one of its Factors?
My math teacher asked me this problem for homework and I am unsure how to solve it.
Which numbers contain a number of factors equivalent to the value of one of their divisors?
I found that 8 works, ...
- 171
-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}}$
- 9
1
vote
2
answers
60
views
How to proof $a = \left\lfloor\frac{Log(N)}{Log(P)}\right\rfloor$ is the maximum exponent of prime P such that $P^a \le N$
I'm trying to solve Project Euler's Problem #5 which is:
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to N?
I came across a solution here using prime ...
3
votes
1
answer
106
views
Divisibility proof through prime-factorization.
I have to show that the following expression:
$$ \frac {1}{2} (3^{2^{n}}-1) $$
can be divided by $n-1$ different and odd prime numbers for every positive $n$ (I assume that $n \in \mathbb{N^*}$ )
So ...
- 429
3
votes
1
answer
144
views
Is it possible to "massage" (via shear transformations) a parallelogram with integer-coordinate vertices into an axis-aligned rectangle?
(The problem is my original, unless there's prior art I'm unaware of.)
Given a parallelogram whose vertices have all integer coordinates, you can give it a "massage". Each "move" ...
0
votes
1
answer
345
views
Find the greatest number that will divide 43, 91 and 183 so as to leave the same remainder in each case.
I KNOW THIS IS SOLUTION BUT I DON'T KNOW WHY?
We first find the difference of the numbers and then find the HCF of the got numbers.
183−91=92
183−43=140
91−43=48
Now find HCF of 92, 140 and 48, we get
...
-2
votes
2
answers
159
views
Condition in Type of Prime Factors of Consecutive Integers
We define a odd-prime $p$ as $i$-type prime if $p \equiv - i \pmod q$ where $ 1 \leq i \leq q-1$ (see similar definition on page 24, CHAPTER 2, of the book "Summing It Up" by Avner Ash ...
2
votes
2
answers
234
views
The product of the ages of someone's children
Maria's children are all in school - and their ages are all whole numbers. If the school only takes children from $5$ up to $18$ years and the product of the children's ages is $60,060$ - how many ...
- 25
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
1
answer
41
views
How many numbers between 1 and 1,000 (both inclusive) are divisible by at least one of the prime between 1 to 50? How can I find this? [closed]
I was trying to solve a compettive programming problem in which constraints are so high so I want to deduce a formula for it so that i could do it for other ranges as well.
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
- 9
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 ...
- 15
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 $\...
user635053
2
votes
1
answer
50
views
Implications of representative of $p$-adic factor $g$ of $f$ dividing $f$ in $\mathbb{Z}[X]$
The problem is from this paper (click for pdf) by Mark van Hoeij.
Let $f \in \mathbb{Z}[X]$ be monic and squarefree.
Let $B$ be a Landau-Mignotte bound for $f$, i.e. for any rational factor $\phi$ ...
- 1,118
8
votes
1
answer
635
views
How many integers are there that are not divisible by any prime larger than 20 and not divisible by the square of any prime?
I tackled the problem in the following way but i'm not sure if i'm correct.
I need the count of the numbers that have in their prime factorization only primes p such that $p \lt 20$ and those ...
1
vote
1
answer
51
views
Is brute force trial the only approach to find smallest k such that (840k + 3) is a multiple of 9?
The following is the answer approach given for the below problem in my old book. I am skeptical about the brute trial approach suggested (though k is found after 2 trials in this case). Is there a ...
- 175
1
vote
0
answers
181
views
Question about Zeta-distribution regarding divisibility by primes
For $s>1$ the Riemann Zeta-function is $$\zeta(s)=\sum_{n=1}^{\infty}n^{-s}$$
For a random variable $X$ with values in $\Bbb{N}$, its distribution is given by
$$\Bbb{P}[X=n]=\frac{n^{-s}}{\zeta(s)...
- 2,469
0
votes
1
answer
196
views
Calculate all prime numbers $x$, where $x^{18} - 1$ is divisible by $28728$
Question: Calculate all prime numbers $x$, where $x^{18} - 1$ is divisible by $28728$
Apparently, the answer is all prime numbers except $2, 3, 7,$ and $19.$ I did some prime factorisation and found ...
- 315
5
votes
1
answer
195
views
Find all $n$ such that $n/d(n) = p$, a prime, where $d(n)$ is the number of positive divisors of $n$
Let $d(n)$ denote the number of positive divisors of $n$. Find all $n$ such that $n/d(n) = p$, a prime.
I tried this, but only I could get two solutions.
I proceeded like this -
Suppose
$$n = p^r \...
user636268
0
votes
1
answer
477
views
Find numbers with n-divisors in a given range
I'm trying to answer this question.
Are there positive integers $\le200$ which have exactly 13 positive divisors? What about 14 divisors? If yes, write them. If no, explain why not.
Because I'm ...
user432382
1
vote
1
answer
84
views
Probability for composite $n$ to have prime factor $\geq \sqrt n$
Let $\operatorname{GPF}(n)$ denote the largest prime factor of
$n\in\mathbb N_{>1}$. My computer tests for intervalls $[m,n]$, where $n<10,000,000$, suggests that the probability
$\operatorname{...
- 13.9k
0
votes
2
answers
118
views
Determine the number of positive integers $a$ such that $a\mid 9!$ and gcd $(a, 3600)=180$.
Determine the number of positive integers $a$ such that $a\mid 9!$ and gcd $(a, 3600)=180$.
What I know as of now is that $180\mid 9!$ and that $180\le a\le9!$.
The prime factorization of 180 is $(...
- 23
1
vote
1
answer
102
views
Checking if the Product of n Integers is Divisible by Prime N
Given $n$ integers, $x_1, ... , x_n$, is there some well-known procedure or algorithm that checks if the product $x_1 * ... * x_n$ is divisible by some arbitrary prime $N$ using minimal space?
Since ...
- 315
3
votes
3
answers
185
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 ...
- 51
3
votes
0
answers
61
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
$...
- 221
9
votes
4
answers
1k
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,...
- 4,322
-1
votes
2
answers
180
views
fundamental theorem of arithmetic word problem [duplicate]
Hi here is the question I have in hand:
There are $1000$ empty baskets lined up in a row. A monkey walks by, and puts a banana in each basket, because this is a word problem,
and that is what a ...
0
votes
1
answer
99
views
Working with divisor function
So by Fundamental Arithmetic Theorem, any integer has a unique prime factorization into primes, written as:
$$n=p_1^{k_1}p_2^{k_2}p_3^{k_3}...p_r^{k_r}$$
From exponents $k_1,...k_r$ it is possible to ...
0
votes
1
answer
195
views
Finishing the task to find the solutions of $\frac{1}{x}-\frac{1}{y}=\frac{1}{\varphi(xy)},$ where $\varphi(n)$ denotes the Euler's totient function
In this post I evoke a variant of the equations showed in section D28 A reciprocal diophantine equation from [1], using particular values of the Euler's totient function $\varphi(n)$. I ask it from a ...
user243301
10
votes
4
answers
13k
views
How to get all the factors of a number using its prime factorization?
For example, I have the number $420$. This can be broken down into its prime factorization of $$2^2 \times3^1\times5^1\times7^1 = 420 $$
Using $$\prod_{i=1}^r (a_r + 1)$$ where $a$ is the magnitude ...
- 453