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

learn more… | top users | synonyms

29
votes
0answers
685 views

How to solve this two simultaneous “divisibilities” : $n+1\mid m^2+1$ and $m+1\mid n^2+1$

Is it possible to find all integers $m>0$ and $n>0$ such that $n+1\mid m^2+1$ and $m+1\,|\,n^2+1$ ? I succeed to prove there is an infinite number of solutions, but I can not progress ...
11
votes
0answers
111 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 ...
11
votes
0answers
257 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 ...
10
votes
0answers
253 views

What's the most efficient algorithm for Divisibility?

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
9
votes
0answers
127 views

Remainder of dividing $3^n$ by $2^n$.

I'd like to find the remainder of dividing $3^n$ by $2^n$, that is, I'd like to find value of $r$ in the expression $$3^n=q2^n+r,$$ where $q\in\mathbb{Z}$ and $0<r<2^n$. I know that it can be ...
7
votes
0answers
78 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 ...
7
votes
0answers
83 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 ...
7
votes
0answers
502 views

Natural extension of the divisor function $\sigma$ to the complex integers $\mathbb{Z}[i]$

The divisor function $\sigma$ of a positive integer $n$ is defined as the sum of the positive divisors of $n$. It turns out that this definition is equivalent to ...
6
votes
0answers
64 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 ...
6
votes
0answers
213 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 ...
5
votes
0answers
61 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 ...
5
votes
0answers
60 views

Smallest $n$-digit number $x$ with cyclic permutations multiples of $1989$

Suppose $x=a_1...a_n$, where $a_1...a_n$ are the digits in decimal of $x$ and $x$ is a positive integer. We define $x_1=x$, $x_2=a_na_1...a_{n-1}$, and so on until $x_n=a_2...a_na_1$. Find the ...
5
votes
0answers
116 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 ...
5
votes
0answers
232 views

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have?

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have? options given: (a) either $1$ or $2$ (b)$1$ or $3$ (c)either $2$ or ...
5
votes
0answers
97 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$ ...
4
votes
0answers
37 views

Functional division $\max(f(x+y),f(x-y))\mid \min(xf(y)-yf(x), xy)$

As the title suggests, the problem here is: Find all functions $f:\mathbb{Z}\to\mathbb{N}$ such that, for every $x,y\in\mathbb{Z}$, we have $$\max(f(x+y),f(x-y))\mid \min(xf(y)-yf(x), xy)$$ I ...
4
votes
0answers
75 views

What is the smallest prime factor of the number $14^{14^{14}}+13\ $?

What is the smallest prime factor of the number $$N\ :=\ 14^{14^{14}}+13\ ?$$ The number of digits of $N$ is $12,735,782,555,419,983$ (The number of digits of $N$ has itself $17$ digits). The first ...
4
votes
0answers
64 views

Systems of linear modular equations with unknowns in the moduli

I am interested in systems of linear modular equations, where the unknowns also appear in the moduli. The general form would be: $A \vec{x}= \vec{b} \;\textrm{mod} \; (C \vec{x}+\vec{d})$ where A ...
4
votes
0answers
132 views

Connections between Fibonacci and natural numbers

Here are some known facts about the Fibonacci numbers and then some questions regarding them . 1.Carmichael's theorem : For every $n>12$ $F_n$ has a prime divisor which doesn't divide any of ...
4
votes
0answers
76 views

$d$ and $d+1$ both dividing certain integers

\begin{align} & 1\cdot 72 \\ & 2\cdot 36 \\ & 3\cdot 24 \\ & 4\cdot 18 \\ & 6\cdot 12 \\ & 8\cdot 9 \end{align} When the divisors of a number are listed in this way, let us ...
4
votes
0answers
91 views

When is ${(1-t^2)^{-N/2}}{\det(f_t(A))}$ expressible as polynomial?

Given a matrix valued function $f_t:\mathbb R^{N\times N} \mapsto \mathbb R^{N\times N}$. For $f_t(A)=B$ both $A$ and $B$ are symmetric. Which properties can be assigned to $f_t$, when the following ...
3
votes
0answers
64 views

When does $a^b\mid b^a$

Let $a,b >1$ be integers. When does $a^b \mid b^a$? Certainly if this is true then $a\mid b$ by considering $a$'s prime factors. (not quite convinced). Also then if $b$ is prime then $a=b$. ...
3
votes
0answers
280 views

The Divisors of $s(2s+1)$ and Primes $2n+1$ and $3n+1$ part 1

I want to check my math (and proof) on the following claim. The claim is by way of a computer search and a "hunch". claim: If $s$ is a prime number I write $\varphi_{s} =s(2s+1)$. Let $\tau$ be ...
3
votes
0answers
58 views

An upper bound for the number of answers of this equation

Let $n$ be a natural number and $p$ a prime number less than or equal to $n$. $$\begin{align} n^2 + 2n &\equiv a \pmod p\\ n^2 + 1 &\equiv b \pmod p \end{align}$$ If $a \lt b$, $p$ is ...
3
votes
0answers
18 views

Knapsack - Saving Waste

I am trying to figure out the most efficent way to save waste. I've looked into the knapsack problem as I believe it is what can help me solve this dilemma. Any help, guidence, or direction is ...
3
votes
0answers
38 views

Prove that $2\mid x$ and $5\mid x$ if and only if $10\mid x$

I have to do it without using Fundamental Theorem of Arithmetic. Can someone check my work? Prove if $2\mid x$ and $5\mid x$, then $10\mid x$. Let $x \in \mathbb{Z}$. Suppose $2\mid x$ and $5\mid ...
3
votes
0answers
88 views

$1+2^x+\ldots+n^x \mid 1+2^y+\ldots+n^y$ for all $n$ implies $x=y$?

The following problem was proposed by A. Schinzel a couple of days ago at the 22nd Conference on Number Theory, held in Liptovsky Jan (Slovakia). He pointed out that the question has an affirmative ...
3
votes
0answers
102 views

Lehmer's totient problem generalization (adding a constant )

Lehmer's totient problem is an well-known open problem which states that the divisibility : $$\phi(n) \mid n-1$$ holds only for primes . This motivated me to ask the following : For which ...
3
votes
0answers
36 views

Is there a name for the least exponent $e$ such that a power of an integer is divisible by another?

Say the primes dividing $m$ also divide $n$. Is there a name for the least exponent $e$ such that $m | n^e$? I can write that explicitly using the prime factorizations of $m$ and $n$, but am ...
3
votes
0answers
58 views

Why is this not a poset after adding zero?

The problem    Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
3
votes
0answers
83 views

Trying to prove a congruence for Stirling numbers of the second kind

I am struggling with a demonstration for this: When $n$ and $m$ are 2 natural integers such that $n-m$ is odd, then the following congruence holds for Stirling number of the second kind ${n \brace ...
3
votes
0answers
62 views

Multiple of $n$ and the sum of its digits is $k\geq n$.

Show that for every positive integers $k\geq n$, with $n$ not divisible by $3$, there is a positive integer divisible by $n$ and such that the sum of his digits is $k$.
3
votes
0answers
50 views

GCD-Domain and proprieties

Let $A$ be a commutative GCD-domain (not necessary UFD or Bezout) and $a,b,c$ elements of $A$ such that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$. Is it true that $\gcd(ab,c) = 1$ ?
3
votes
0answers
60 views

Generating all lesser numbers of two coprime numbers

Let's say I have two coprime positive integers, $a$ and $b$. How would you go about proving that it is possible to make all integers between 1 and $max(a,b)$ by subtracting them from each other? For ...
3
votes
0answers
96 views

Find Gcd summation fast?

Find the value of the summation: $$ val=\left( \sum_{i=1}^a \sum_{j=1}^b\sum_{k=1}^c....\sum_{x=1}^p GCD(i,j,k,..x) \right)$$ Contraints $2\leq$number of summation terms$\leq 500$, $1\leq ...
3
votes
0answers
137 views

When is a number like “ddd…ddd”+1 (where d is a digit) a perfect square or a prime?

Inspired by Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?, I wonder when numbers like these are perfect squares. Certainly, all numbers of the form $000...0001$ are ...
3
votes
0answers
700 views

Show that if both a, b are even integers not both 0, then $(a, b) = 2 (a/2, b/2)$

Show that if both a, b are even integers not both 0, then $(a, b) = 2 (a/2, b/2)$. Hi there, I want to know if the following proof I have is strong enough, or if I'm making false assumptions :|. ...
3
votes
0answers
109 views

Find the fundamental group and the Alexander polynomial

I would like to find the Alexander polynomial of the link $L$, described below. Let $K(q,r)$ be the $(q,r)$-torus knot embedded on a torus $V$. Inside the torus $V$, consider a smaller solid torus ...
2
votes
0answers
43 views

If $k(a^2+mb^2) = c^2+md^2$, what can be said about the form of $k$?

Let $k,a,b,c,$ and $d$ be integers, and let $m \ge 2$ be a non-square integer, such that $$ k(a^2+mb^2) = c^2+md^2. $$ QUESTIONS: What can be said about the form of $k$ with no further ...
2
votes
0answers
55 views

Prove or disprove $a^2\mid b^3\Longrightarrow a\mid b$

I need to prove or to give a counter-example: $$a^2\mid b^3\Longrightarrow a\mid b$$ My attempt: First, let's check with small integres,trying to find counter-example: $2^2\mid ...
2
votes
0answers
135 views

Prove that $(a-b)^n\mid (a^n-b^n) \iff n=1$ under given conditions

Suppose that $a,b,(a-b)$ are pairwise co-prime (i.e. $a\perp b\perp (a-b)\perp a$), and that $\frac{a}{2}<b<a$, where $a$ and $b$ are both positive integers greater than $2$. Let $n$ be odd. ...
2
votes
0answers
50 views

If $a^n+n^b\mid c^n+n^d$ for every $n$ then $c=a^k$ and $d=kb$ .

I made a generalization of the following problem (it's a problem from the IMO shortlist in some year) : Let $a,b$ be fixed positive integers . If : $$a^n+n \mid b^n+n$$ for every positive integer ...
2
votes
0answers
52 views

Can Someone approve the formula for the number of groups of order $p^2q$

Here https://www2.bc.edu/~reederma/Groups.pdf on page $112$, a table of the number of groups of order $p^2q$ is given. In the explanations, there is a typo ($\frac{q+5}{5}$ instead of ...
2
votes
0answers
38 views

How many sequences of the form $1a_1a_2…a_n1$ have each $a_i$ dividing the sum of its two neighbors?

For each $n \in \mathbb{N} $, how many sequences of the form $1a_1a_2...a_n1$ with the $a_i \in \mathbb{N}$ have each $a_i$ dividing the sum of its two neighbors? I just came across this, and ...
2
votes
0answers
42 views

Determine All Divisors of $f(x)=x^n\in F[x]$

Carefully determine all divisors of $f(x)$ where $$ f(x)=x^n\in F[x]$$ note that $F[x]$ is a Field So, $$ \underbrace{x^0\mid x^n,\ x^1\mid x^n,\dots,\ x^n\mid x^n}_{n+1}$$ making $n+1$ divisors. ...
2
votes
0answers
41 views

Divisibility of factorials

There are two numbers, $n$ and $p$, with prime $p$ and $n < p$. One is to calculate $n! \bmod p$. Is there any chance of doing this without explicitly determining $n!$ ? I already know that with ...
2
votes
0answers
52 views

How can I construct a number $n$, such that $gcd(n+k,100!)\ne 1$ for all $k=0,…,256$

Here : https://oeis.org/search?q=2%2C4%2C6%2C10%2C14%2C22%2C26%2C34%2C40%2C46&sort=&language=german&go=Suche it is indirectly claimed that there exists a number $n$, such that $n+k$ has ...
2
votes
0answers
36 views

About the least common multiple of numbers and combinatorial

Prove that for any positive integer $n$, the least common multiple of the numbers $1, 2, 3, \ldots , n$ and the least common multiple of the numbers: ${n\choose 1}, {n\choose 2}, \ldots , {n\choose ...
2
votes
0answers
49 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 ...
2
votes
0answers
31 views

$m+n = (n,m)^2; n+l = (n,l)^2; l+m = (m,l)^2$

Find all natural numbers $m,n,l$ such that $$m+n = (n,m)^2; \quad n+l = (n,l)^2; \quad l+m = (m,l)^2$$ where $(a,b)$ is the greatest common divisor of $a$ and $b$. I only managed to find that if ...