Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [divisibility]

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

20
votes
0answers
475 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 ...
20
votes
0answers
492 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 ...
19
votes
0answers
283 views

How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?

For the numbers $1, \ldots, N$, how many ways can I arrange them such that either: The number at $i$ is evenly divisible by $i$, or $i$ is evenly divisible by the number at $i$. Example: for N = 2$, ...
13
votes
0answers
699 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, ...
12
votes
0answers
406 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 ...
11
votes
0answers
334 views

Divisibility of term in exponential recurrence relation

I found the problem here: http://www.artofproblemsolving.com/community/c7h1314296_2x15_is_divisible_by_x $\large a_1 = 3$ $\large a_{n+1} = 2^{a_n -1} +5$ Prove: $\large a_n|a_{n+1}$ Initially I ...
9
votes
0answers
449 views

An interesting problem which only needs elementary number theory

A problem about elementary number theory While writing my paper, I came across the following problem: (all the discussion assume that $q$ is prime and $\alpha $ is a positive integer. ) We first ...
8
votes
0answers
123 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 ...
8
votes
0answers
141 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
221 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 ...
7
votes
0answers
871 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 $$\sigma(n)=\prod_{\substack{p^\alpha|...
6
votes
0answers
252 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. ...
6
votes
0answers
135 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 ...
6
votes
0answers
76 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 ...
6
votes
0answers
80 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 ...
6
votes
0answers
108 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$...
6
votes
0answers
381 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
192 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
258 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 the ...
5
votes
0answers
242 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$ ...
4
votes
0answers
65 views

On two nested radicals and divisibility

The last days I was playing around with two nested radicals which, as I learned here, can be simplified: $$u(x) =\sqrt{x + \sqrt{x +\sqrt{x +\sqrt{x +...}}}} = \frac{1}{2}(1+\sqrt{1+4x})$$ $$l(x) = \...
4
votes
0answers
53 views

Non-Chen primes dividing $3^k+3$ and $2^k-3$

A non-Chen prime is a prime $p$ such that $p+2$ is neither a prime nor a semi-prime. $3^6+3=732$ is divisibile by the non-Chen prime $61$. On the other hand, $2^6-3=61$. Are there infinitely many $...
4
votes
0answers
95 views

If $\langle g \rangle$ is the only subgroup of order $p$, what's the order of elements $xg$?

Somewhat getting distracted from an exercise, I noticed that if a group $G$ has only one subgroup of order $p$ where $p$ is a prime (so our subgroup is wlog generated by $g$), any conjugation $$xgx^{-...
4
votes
0answers
78 views

Can we find all solutions to the equation $\frac{\phi(n)}{\phi(n-1)}=5$, where $\phi(n)$ denotes the totient function?

The solutions of the equation $$\frac{\phi(n)}{\phi(n-1)}=5$$ upto $n=10^8$ , where $\phi(n)$ denotes the totient function, are : ...
4
votes
0answers
112 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
163 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 ...
4
votes
0answers
796 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 $3$ (...
4
votes
0answers
95 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
94 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
86 views

Elementary number theory proofs

I am a freshman studying computer science, and I am supposed to solve this problem for my '(introduction to) elementary number theory' course. Could someone give me a hint or two on how to solve the ...
3
votes
0answers
58 views

About the prime divisor of a quadratic function

Encountered in Modell's book Diophantine Equations. In the second chapter, page 3, it says: 'every prime divisor of $p$ of $x^2-a$ for integer $x$ is either a divisor of $a$, or can be represented ...
3
votes
0answers
46 views

Sum of elements of order dividing a divisor of $p-1$ in the group of units of $\mathbb{Z}/p\mathbb{Z}$

Let $p$ be a prime number. Let $U(\mathbb{Z}/p\mathbb{Z})$ denote the group of multiplicative units in $\mathbb{Z}/p\mathbb{Z}$. It is well-known that $U(\mathbb{Z}/p\mathbb{Z})=\{1,2, ..., p-1\}$ ...
3
votes
0answers
51 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 $...
3
votes
0answers
64 views

Prove that if $p$ is a prime number, then $p|n^p-n$

Prove that if $p$ is a prime number, then $p|n^p − n$ for $n ≥ 1$ I tried proof by induction for this but was not able to even prove the base case (I tried it for $n=1$ since we're trying to prove ...
3
votes
0answers
74 views

Find if x is divisible by a number in the sequence from 2 to p

What's the best way ( in terms of complexity ) to find if $x$ is divisible by any number between $2..p$ ( inclusive), the obvious solution is to iterate over all numbers $i$ between $2$ and $p$ and ...
3
votes
0answers
78 views

Pell number factorization and divisibility question

In a problem I’m working on, I have positive integers $a,b,c,d$ satisfying $$ (ab)^2-2(cd)^2=1. \tag{1} $$ Furthermore, I’ve determined that \begin{align} a &\mid (b^2+2c^2) \\ b &\mid (a^2-...
3
votes
0answers
45 views

Number theory proof: Let $w=a+\sqrt{3}\cdot b$ where $w\neq 0$. Let $|N(w)| = 3^{a}\cdot k$, where $3\nmid k$…

Let $w$ be an extended integer (of the form $a+b\sqrt{3}$) with $w\neq 0$. Let $|N(w)| = 3^{a}\cdot k$, where $3\nmid k$ (See hw 4). Prove that there exists am extended integer $z$ such that $w = (\...
3
votes
0answers
46 views

Assume $d\mid n$ and $\gcd(a,d)=1$. Let $t$ be the product of prime numbers that divide $n$, but don’t divide $a$. Show: $\gcd(a+td,n)=1$.

Let $d,n\in\mathbb Z_{>0}$ with $d\mid n$. Let $a\in\mathbb Z$ such that $\gcd(a,d)=1$. Let $t$ be the product of prime numbers that divide $n$, but don’t divide $a$. Show: $\gcd(a+td,n)=1$. ...
3
votes
0answers
56 views

Fibonacci Numbers, Necklaces, Number Theory (modulo 10)

Given 2 numbers a and b form a "necklace" by adding them together mod 10, taking the last 2 numbers in the sequence, adding them mod 10 and so on until you get back to the start. E.g With 1 and 8: ...
3
votes
0answers
78 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
63 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 $...
3
votes
0answers
77 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
31 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
98 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
46 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
42 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 $d ...
3
votes
0answers
112 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
159 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 m}...
2
votes
0answers
48 views

Is there an easy criterion when $\binom{n}{m}$ is divisible by $q^2$?

To analyze questions like this On variations of Erdős squarefree conjecture: presentation and a question as a simple case it would be nice to have a simple criterion when $\binom{n}{m}$ is ...
2
votes
0answers
99 views

On a conjectured relationship between the least prime factor and the Euler prime of an odd perfect number

(Note: This question has been cross-posted to MO.) Let $\sigma$ be the classical sum-of-divisors function. For example, $$\sigma(6)=1+2+3+6=12={2}\cdot{6}.$$ If $\sigma(N)=2N$ and $N$ is odd, then $...