# Questions tagged [divisibility]

This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

620 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

### Have I discovered an analytic function allowing quick factorization?

So I have this apparently smooth, parametrized function: The function has a single parameter $m$ and approaches infinity at every $x$ that divides $m$. It is then defined for real $x$ apart from ...
• 1,091
917 views

### Is $\frac{(p-1)^p+1}{p^2}$ square-free?

Is $\frac{(p-1)^p+1}{p^2}$ squarefree for all primes $p \geq 7$? I did some small testing and it seems to hold up to $p \leq 47$. Also, note that the above expression is indeed an integer by binomial ...
1k views

### Dividing the whole into a minimal amount of parts to equally distribute it between different groups.

Suppose we have a finite amount of numbers $x_1, x_2, ..., x_n$ ($x_i\in\mathbb{N}$) and an object that should be divided into parts in such a way that it can be without further dividing distributed ...
• 3,222
2k views

### How to find the approximate basic period or GCD of a list of numbers?

I want to tell the number which act as the best approximate basic period (or wavelenght as pointed out by Eric) of a list of real numbers: e.g for {14, 21, 35} we should obtain 7 as the basic period, ...
• 366
217 views

• 1,749
302 views

### Why is there an unexpected increase in the density of certain types of Goldbach primes?

Note: Posted in MO since it is unanswered in MSE. I was checking how quickly we can verify Goldbach's conjecture for a given even number $n$ and it was clear that backward starting from the largest ...
• 20.9k
386 views

### Making binomial coefficients out of binomial coefficients

For binomial coefficients, we have $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ Now, fix a positive integer $s$ and define a function $n?=\binom{n}{s} \cdot \binom{n-1}{s} \cdot ... \cdot \binom{s}{s}$ or $1$ ...
• 2,196
143 views

### Which prime factors of $8^{8^8}+1$ are known?

We have the partial factorization $$8^{8^8}+1=(2^{2^{24}}+1)\cdot (2^{2^{25}}-2^{2^{24}}+1)$$ The first factor is $F_{24}$. It is composite, but no prime factor is known. A prime factor of the second ...
• 85.2k
197 views

### Generalisation of $\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n\gcd(a,b)^{n-1},a-b)$ to $\gcd\left(\frac{a^n-b^n}{a-b},a^m-b^m\right)$?

We have the identity $$\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n\gcd(a,b)^{n-1},a-b).$$ (see here) This appears to be a quite useful result with various applications. I wonder whether there is ...
• 26.5k
173 views

### What is the density of numbers which have at least two divisors whose sum is a perfect square?

Update: Posted in MO since it is unanswered in MSE after 2 years. A positive integer is said to have square-sum divisors if it has at least two divisors whose sum is a perfect square. $6$ has square-...
• 20.9k
234 views

### Finding solutions to a symmetric divisibility condition $x\mid p(y),\;y\mid p(x)$

In general, are there strategies for finding all integers $x$ and $y$ such that $x \mid p(y)$ and $y \mid p(x)$ for some polynomial $p$ with integer coefficients? For example, could we find all ...
• 5,521
674 views

### On divisors of $p^n-1$

This question raised from discussions around my previous question. This may seem trivial or easy, but I am so confused and can't see the answer. So I will be so grateful if you would help me please. ...
• 123
166 views

### Integer divisibility

Given a (not strictly) decreasing sequence of natural positive numbers $a_1, a_2, \dots, a_n$ prove that $$\prod_{i<j} j-i \quad\big|\quad \prod_{i<j} a_i - a_j - i +j$$ I already know a ...
• 11.4k
99 views

### Show there are only a finite number of integers with $\dfrac{\prod_{i=1}^n a_i-1}{\prod_{i=1}^n (a_i-1)}$ an integer

Show, for each $n$, there are only a finite number of integral $(a_i)_{i=1}^n$ such that $2\le a_i \le a_{i+1}$ and $\dfrac{\prod_{i=1}^n a_i-1}{\prod_{i=1}^n (a_i-1)}$ is an integer. My question is ...
• 109k
255 views

### When $\frac{1}{n}\binom{n}{r}$ is an integer , again?

This question follows a previous one If $n$ and $r$ are coprime then $a_{n,r}=\frac{1}{n}\binom{n}{r}$ is integer but this is not a necessary condition. Question: what is a necessary and ...
• 3,716
138 views

### Divisibility sequence resulting in limit with pi

Consider the following sequence of operations : Start with a natural number $n$ and then round it up to the closest multiple of $n-1$ .Then round up this new number to the closest multiple of $n-2$...
204 views

### Solving a Diophantine equation3

The Diophantine equation that I have to solve is: $$343x^2-27y^2=1$$ This question has already been posted by other user but it has not received an answer. I proved to solve it. This is my attempt: ...
• 2,682
482 views

### Reducing multivariate rational fractions to lowest terms

I wish to simplify multivariate rational fractions to a canonical form. Thanks to some very helpful mathematically inclined people who verified that my understanding of Wikipedia was correct, I'm now ...
312 views

### Extention of Euclid's GCD Algorithm. (The Art of Computer Programming, Volume 1, Edition 3, Section 1.2.1, Exercise 12)

Euclid's GCD algorithm which is used to find GCD of two input numbers, say, $c$ and $d$, needs the inputs to be positive integers. Exercise 12 provides an extension to this algorithm and allows $c$ &...
• 193
227 views

• 2,088
230 views

### Unique solution to $\frac{n}{\pi(n)}=k$

Let $\ k\$ be a positive integer and $\ \pi(n)$ the number of primes not exceeding $\ n\$ (The prime counting function). Is the solution $\frac{n}{\pi(n)}=k$ unique only for $\ k=11$ ? It is known ...
• 85.2k
95 views

• 968
51 views

### Testing if a number has a positive divisor of a specific form

My problem is the following: Given a positive integer $n$, determine if $n$ has a divisor of the form $d=3+8k$ where $k$ is a non-negative integer. I'm aware there are fast algorithms for checking ...
• 41
131 views

### Prove that $(a^6+b^6-1)(a^6+b^6-2)$ is divisible by $252$ if $a$ and $b$ are coprime integers

Prove that $(a^6+b^6-1)(a^6+b^6-2)$ is divisible by $252$ if $a$ and $b$ are coprime integers. I thought about proving that this number is divisible by $2$, $3$ and $7$ but I don't know how should I ...
• 51
148 views

### Two numbers with a given difference having the same number of divisors

So, it is required to prove that for each natural $k$ there are two natural numbers with a difference $k$ having the same number of divisors. For example, for the case $k=27$, the pair $(18,45)$ is ...
• 2,334
127 views

### Find a positive integer $i$ such that $9i + 1$ divides $2 \times 10^i - 1$

I have written a Python program running over $i$, but up to billions there is no solution, so I guess there is no solution. Trying to prove that, I looked at multiplicative order, but I do not get a ...
• 594
129 views

### Show that for all $n$ there exist some $n$-digit number with no $0$ in it whose digit sum divides it.

$\textbf{Question:}$Prove that for each positive integer $n$, there exists a positive integer with the following properties: • it has exactly $n$ digits, • none of the digits is $0$, • it is divisible ...
• 1,854
61 views

### How to decide whether $n+\varphi(n)$ can divide $n^2+k$?

How can we decide whether for a given positive integer $k$ , $\varphi(n)+n$ can divide $n^2+k$ , where $\varphi(n)$ denotes the totient function ? Some cases are easy : $n=1$ is a solution for odd $k$...
• 85.2k
136 views

### How many divisors of $\phi(m)$ do not divide $m-1$?

Lehmer's totient problem asks if there exists a composite number $m$ such that $\phi(m)$ divides $m-1$. Lower bounds on $m$ has been established but we do not know if a solution exists. Clearly, if we ...
• 20.9k