Questions tagged [divisibility]
This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.
6,096
questions
-1
votes
1
answer
51
views
Approaching a Divisibility Question
Perhaps I'm a bit rusty on my number theory, but I have been struggling to figure out how to determine what positive integers $x$ and $y$ satisfy
$$ x+y \text{ divides } x^2 + y^2 $$
Any thoughts? I ...
- 2,691
1
vote
0
answers
39
views
$(a^m+b^m)\mid(a^n+b^n) \iff m\mid n$ [duplicate]
Prove that $(a^m+b^m)\mid(a^n+b^n) \iff m\mid n$. Here $a, b, m, n\in\mathbb{Z}^+$, $m\leq n$ and $(a, b)=1$.
This is a questions from a number theory book that I am recently studying.
I have read ...
- 2,920
1
vote
1
answer
52
views
How to logically represent a smaller number being divided by a large number on a number line?
Recently I asked this question on this platform:
When we divide a number by another number ($x \div y$), we can interpret it in two ways:
$x$ is divided in equal groups, where each group consists of $...
- 73
-4
votes
0
answers
53
views
Find the values of integers A and N (≥A) for which (3ᴬ - 2ᴬ)/(2ᴺ - 3ᴬ) is a positive integer
Is there any way to find the values of integers A and N (≥A) for which (3ᴬ - 2ᴬ)/(2ᴺ - 3ᴬ) is a positive integer?
I'm trying to disprove the Collatz Conjecture:
...
3
votes
0
answers
110
views
How many 7-digit numbers with distinct digits can be made that are divisible by 3?
How many 7-digit numbers with distinct digits can be made that are divisible by 3?
First of all, I counted all the ways to insert 7 of 10 digits in a number making the number divisible by 3.
Digits ...
- 31
-3
votes
0
answers
47
views
Prove that $n^7-n$ is divisible by $42$ [duplicate]
Prove that $n^7-n$ is divisible by $42$ for all $n$.
I have proven one part using induction, but how do I prove the other one?
- 1
2
votes
1
answer
117
views
Prove The Divisibility rule of 19 [duplicate]
I'm a beginner in number theory, I was trying to prove the divisibility rule of 19, can someone help me to complete my proof
Let $n$ be $10a + b$ where b is the unit digit and 10a is the rest; 10 is ...
- 147
-3
votes
1
answer
84
views
Can someone simplify this maths question for my tiny brain to understand? [closed]
My maths teacher gave me this question, but i have no clue what it means:
The nine numbers $p_1,p_2 ... ,p_9$
are distinct primes.
$N$ positive integers are chosen, where $N$ is a multiple of 100, so ...
4
votes
1
answer
140
views
BMO1 number theory question on fibonacci sequence and divisibility
This is question 2 from the 1983 British Maths Olympaid
The fibonacci sequence $f_{n}$ is defined by $f_{1} = 1, f_{2} = 1,$ and $f_{n} = f_{n-1} + f_{n-2}, n > 2$
prove that there are integers a,...
- 169
0
votes
5
answers
91
views
How to logically interpret the division of small number by large number on a number line?
When we divide a number by another number ($x \div y$), we can interpret it in two ways:
$x$ is divided in equal groups, where each group consists of $y$
$x$ is divided in $y$ equal groups
Suppose ...
- 73
0
votes
2
answers
88
views
How many 6-digit numbers of the form xyzzyx (where y is a prime number) are possible which are divisible by 7?
How many 6-digit numbers of the form $xyzzyx$ (where $y$ is a prime number) are possible which are divisible by 7?
My try: Since we were checking for a multiple of 7, I tried using the 7 divisibility ...
- 398
2
votes
2
answers
95
views
positive integers property
The positive integers are written into rows so that row n includes every integer m with the properties: a) $m$ is a multiple of $n$; b) $m \leq n^2$ ; c) $m$ is not in the earlier row.
Determine the ...
- 438
1
vote
0
answers
37
views
Commutative ring with an element divisible by all powers of $a$ but with no corresponding infinite sequence
Is there a commutative ring $R$ with two elements $a$ and $b$ for which $b \in \bigcap_{n \ge 0} a^nR$ (the intersection of the principal ideals generated by the powers of $a$), but there is no ...
- 9,523
0
votes
0
answers
41
views
When is (a+b+c)(1/a+1/b+1/c) integer [duplicate]
I was a kind of curious over this for past few days,
If $a_1, a_2, a_3$ can be any natural nos, what are the distinct integer values $(a_1+a_2+a_3)(\frac{1}{a_1}+\frac{1}{a_2}+\frac{1}{a_3})$ can ...
- 144
1
vote
1
answer
39
views
Can relative (or even absolute) quotient size be calculated from a list of polynomials which are multiples of a given variable?
I am working on a Diophantine equation in integers $x$ and $y$. The equation has been solved, so I already know the solutions (there are four) — I am trying to find a more elementary solution.
Through ...
- 7,824
1
vote
0
answers
24
views
Proof of existence in division with remainder [duplicate]
Proposition. Let $a\in \mathbb{Z}^+$, $b\in\mathbb{Z}$. Then there exist unique numbers $q,r\in\mathbb{Z}$ such that $b=qa+r; 0≤r<a.$
Proof.
Existence:
Define $S:=\{b-qa \mid q\in \mathbb{Z}, b-qa\...
4
votes
1
answer
143
views
Infinitely many $a_n$ [closed]
Let $\{a_n \}$ be a sequence defined as follows:
$$ \begin{gathered} a_0=0 ; a_1=1 ; a_2=2 \text { and } \\ a_{n+3}=5^n \cdot a_{n+2}+n^2 \cdot a_{n+1}+11 a_n \text { for } n \geq 0 . \end{gathered} $$...
- 85
1
vote
1
answer
32
views
Another Binomial Coefficient Congruence Modulo Prime Powers
I have the following conjecture on binomials modulo prime powers:
Let $s, b, n \ge 0$ be integers, let $p$ be a prime and let $0\le k_0 < p^{b+1}$ and $0\le n_0 < p^{b+s}$, then we have the ...
- 4,512
1
vote
1
answer
59
views
Find all positive integers m so that for $n=4m (2^m - 1)$, $n | (a^m - 1)$ for all a coprime to n
Find all positive integers m so that for $n=4m (2^m - 1)$, $n | (a^m - 1)$ for all a coprime to n.
First, we try $m=1$. Then $n=4$, and clearly it is not true that $4 | (a-1)$ for all odd a.
For $m=2,...
- 863
0
votes
4
answers
188
views
Formally prove that $3^ {80} - 2^{20}$ divisible by $5$ [duplicate]
I am not sure how to formally prove that prove that $3^{80} - 2^{20}$ divisible by $5$; any hints would be much appreciated. My initial approach was to write a table with examples that when both $3$ ...
-1
votes
0
answers
32
views
Show that if n is an odd integer that is not a multiple of 5, then there exists an integer, all of whose digits are 1, that is divisible by n. [duplicate]
For example 7|111111
We have been working with Φ(n) functions but I dont see how these are related
4
votes
1
answer
185
views
What is the remainder when dividing $a$ by $5$ if $\sum_{k=1}^{1992}\frac{1}{k}=\frac{a}{b}$?
Consider
$$\sum_{k=1}^{1992}\frac{1}{k}=\frac{a}{b}.$$
If $a$ and $b$ are natural numbers that are relatively prime, what is the remainder when dividing $a$ by $5$?
$\text{(A) } 0 \space\space\space\...
- 4,868
0
votes
2
answers
48
views
If primes $p_1 \neq p_2$ divide $n$, then $\exists$ $x, y \in G \setminus \{e\}$ such that $\langle{x}\rangle \cap \langle{y}\rangle = \{e\}$
Q: If $G$ is a group with order $n$, and $p_1$ and $p_2$ are distinct primes that divide $n$, show that there exists $x, y \in G \setminus \{e\}$ such that $\langle{x}\rangle \cap \langle{y}\rangle = \...
- 322
0
votes
2
answers
90
views
Find $n$ knowing some divisibilities
Question :
Determine the natural numbers $n$, given that $3^n-1$ is divisible by $2^n$, and given that $4^n-1$ is divisible by $3^n$.
My Idea :
We can say that $4^n \equiv 0 ( \mod 4 )$ , which means ...
- 341
-3
votes
1
answer
56
views
For prime $p$, show that $p\mid a^n\Rightarrow p\mid a$ [duplicate]
I already try to solve this with divisibility rule
$p = ka, a^n$ = $ka*ka$ as much as $n$ times
$a^n≡a (mod n)$, then $p^n=ka*ka$
therefore $p^n= a^n$ be $^n√p^n|^n√a^n$ which $p|a$
but im not sure ...
- 1
3
votes
2
answers
213
views
Solution Verification for RMO (Indian Math Competition)
Let N be the set of all positive integers and $S={(a,b,c,d)\in N^4: a^2+b^2+c^2=d^2}$. Find the largest positive integer m such that m
divides abcd for all (a,b,c,d) \in S (RMO Problem 1: 29 Oct, 2023)...
- 1,456
1
vote
1
answer
57
views
Do exist positive integers $a < b$ with the following property: Whenever $m, n$ are positive integers with $m^a|n^b$ then $m|n$. [duplicate]
Decide with justification if there exist positive integers $a < b$ with the following property: Whenever $m, n$ are positive integers with $m^a|n^b$ then $m|n$.
Here's my attempt at a proof:
Assume ...
- 11
-1
votes
1
answer
101
views
Prove that if $m^2$ is even then $m$ is even [duplicate]
$m, n \in \mathbb{Z}$ $m^2 = 2n^2 \implies m = 2k$ for some $k \in \mathbb{Z}$
In other words, the first statement implies $m$ is divisible by 2. Why?
My professor used this without proving it.
My ...
- 670
0
votes
0
answers
33
views
Why do all parasitic numbers seem to be multiples of repunits?
Let $n$ be a number. Take the last digit of $n$ and move it to the front to produce a new number $m$. If $n$ divides into $m$, then we call $n$ a parasitic number (in base 10). For example, $n = ...
- 407
2
votes
0
answers
66
views
Formulas that generate "too few" primes
I am looking for examples of formulas $f: \mathbf{N} \rightarrow \mathbf{N}$ for which the number of conjectured primes $p \in \text{ Im}(f)$ is either finite or less than what naive heuristics would ...
- 149
-2
votes
1
answer
50
views
Prove that a*b is not divisible by prime number p [duplicate]
Can't understand if my thoughts make sense or not.
The question is the following:
$ab$ is not divisible by prime $p$, if both $a$ and $b$ are not divisible by $p$.
I thought to prove it like this:
For ...
- 1
1
vote
0
answers
51
views
Given $a,b \in \mathbb{N}$, is it true that $\phi(\gcd(a,b))=\gcd(\phi(a),\phi(b))$?
Let $a,b \in \mathbb{N}$ and $d=\gcd(a,b)$. Then we have that $a/d$ and $b/d$ are coprime. I am trying to see if $\phi(a)/\phi(d)$ and $\phi(b)/\phi(d)$ are also coprime ($\phi$ is the Euler totient ...
- 791
0
votes
2
answers
65
views
Find N such that for all x $\ge$ N, $P(x)$ is Divisible by Primes Bigger than 10
Given an arbitrary distinct natural numbers, $d_1, d_2, d_3, d_4,$ and $ d_5$.
Let $P(x) = (x + d_1)(x + d_2)(x + d_3)(x + d_4)(x + d_5)$.
Prove that there is a number $N$ (in terms of $d_1, d_2, ...$...
- 296
-1
votes
2
answers
84
views
The exact meaning of $1/0$?
What is the exact meaning of $1/0$? Does that mean a number that is very large, a number that cannot be expressed as the one we know, infinite numbers of number so that giving one particular value is ...
- 7
4
votes
1
answer
81
views
Prove that there exists a unique partition of $\mathbb{N}$ into A and B so that neither of $A\oplus A$ and $B\oplus B$ has a prime.
For any subset $S\subseteq \mathbb{N}, $ let $S\oplus S = \{a + b : a,b \in S , a\neq b\}$. Prove that there exists a unique partition of $\mathbb{N}$ into disjoint subsets A and B so that neither of $...
- 1,195
1
vote
0
answers
32
views
Prove that ${n\choose k}$ has at least k distinct prime divisors by proving an intermediate statement first
Let $k\in\mathbb{N}$ and let $L_k = lcm(1,2,\cdots, k)$. Let $n\in\mathbb{N}$ with $n\ge k + L_k$. Prove that ${n\choose k}$ is divisible by $\prod_{i=0}^{k-1} \dfrac{n-i}{\gcd(n-i, L_k)}$ and ...
- 863
5
votes
1
answer
116
views
Prove that for all integers $a,b, b\neq 0,$ there exists $n$ with $v_2(n!) \equiv a\mod b$.
Let $v_p(m)$ for a prime p and an integer m be the largest integer d so that $p^d | m$. Prove that for all integers $a$ and $b$ with $b\neq 0,$ there is a positive integer n so that $v_2(n!) \equiv a\...
- 1,195
0
votes
1
answer
65
views
Show that the number isn't divisible by 341 (using congruences & Fermat's little theorem) [duplicate]
Show that the number $3^{341}-3$ isn't divisible by $341$.
We've just covered Fermat's little theorem and linear congruences in my Algebra class.
I've realized that $341 = 11*31$ and I've wrote down:
$...
2
votes
1
answer
99
views
Find all integers $n>1$ with the property that for each positive divisor $d$ of $n$, we also have that: $(d+2) \mid(n+2) $.
Find all integers $n>1$ with the property that for each positive divisor $d$ of $n$, we also have that:
$$
(d+2) \mid(n+2)
$$
So far, I've tried to get as much info about it as possible, but I don'...
- 85
1
vote
1
answer
58
views
Criterion for a factorial ratio to be integral
Let $a_1,a_2,\ldots,a_K,b_1,b_2,\ldots,b_L$ be positive integers. Prove that
$$\frac{(a_1n)!(a_2n)!\cdots (a_Kn)!}{(b_1n)!(b_2n)!\cdots (b_Ln)!} $$
is an integer for all positive integers $n$ if and ...
- 2,650
0
votes
1
answer
61
views
Pick a, b, c randomly without any conditions from the set ${1, 2, 3,..., 2019}$ What is the probability for $abc + bc + c$ to be divisible by 3?
Note: I revisited this problem after I can mostly understand modular arithmetic. Since I was not too satisfied with those answers I decided to try to answer question once again with my own ...
- 165
1
vote
3
answers
83
views
Proving divisibility of a sum $\sum_{k=0}^{\lfloor{n/2}\rfloor} (-1)^{k}\binom{n}{2k} 7^{k}$
I have been given $$
\sum_{k=0}^{\lfloor{n/2}\rfloor} (-1)^{k}\binom{n}{2k} 7^{k}
$$. How can I show that it is divisible by $2^{n - 1}$ for any positive integer $n$? I have attempted to write it in ...
- 15
-3
votes
1
answer
61
views
(Dis)prove $\,a\mid b\,\Rightarrow\, a+b\mid b+c$ [duplicate]
Can someone help me here? I'm completed stuck in this simple problem.
Let a, b, c $\in \mathbb{N} $, check if the statement below is true or false:
if a|b then (a+b) | (b+c)
Any tips?
What i've ...
- 13
0
votes
0
answers
8
views
Proving $n$ divides $φ(a^n − 1)$ for any positive integer $a$ and $n$, where $a^n - 1 > 1$ [duplicate]
How will I be able to show that $n|φ(a^n − 1)$ for any positive integer $a$ and $n$, where $a^n - 1 >1$?
I already have an idea that I will probably need to use cyclotomic polynomials. Will I also ...
0
votes
0
answers
36
views
Relation between two functions with divisibility properties
Given a positive integer $q$ and a finite set $A\subseteq \mathbb{N}$, define the functions
$$
f(q)=\sum_{k=1}^{\infty}\sum_{\substack{n,m\in A \\ n-m=qk}}1 \quad \mbox{and}\quad g(q)=\sum_{\substack{...
- 440
0
votes
1
answer
26
views
Intervals of length $k$ with at least $n$ distinct prime factors
Question: For $k,n\in \mathbb{N}$, what is the smallest $b$ such that there is an interval $N=(b-k,b]\subset \mathbb{N}$ of length $k$ with at least $n$ distinct prime factors dividing the integers $x\...
- 1,860
0
votes
0
answers
86
views
A number with digits $2$ and $5$ is divisible by $2^{2005}$ [duplicate]
I found an old problem on a website but no answer is given. Here is the problem :
Prove that there is a unique positive integer consisting entirely of digits $2$ and $5$, having exactly $2005$ digits ...
8
votes
2
answers
147
views
Prove that there are infinitely many pairs $(m, n)$ such that $(m!)^n + (n!)^m + 1$ is divided by $n + m$.
When I saw factorials, I immediately thought about Wilson's theorem. However, I didn't succeed at all. I also thought about cyclic groups, but with such amount of information I haven't find the use of ...
- 89
0
votes
0
answers
27
views
If a number $n$ shares a common factor with $p^{\alpha}$, then $p|n$. [duplicate]
Let $p$ be prime, $n \in \mathbb{Z}$, $\alpha \in \mathbb{Z}^{+}$. Suppose that $n$ shares a common factor with $p$. I wish to conclude that $p|n$.
The proof follows: If $p$ is prime, then the factors ...
- 274
0
votes
1
answer
67
views
Trouble manipulating quotients in $\mathbb{N}^\times$
As part of a proof about multinomial expansions, I am encountering difficulty in showing the following equality:
$$\frac{k!}{\alpha!} = \frac{(k-\alpha_1)!}{\alpha'!}\frac{k!}{\alpha_1!(k - \alpha_1)!}...
- 1,221