Skip to main content

Questions tagged [divisibility]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
47 views

If prime power divides product of two consecutive integers then, it divides one of them? [duplicate]

Question: If $p^n$ divides product of two consecutive positive integers say, $m(m-1)$ then $\;$ $p^n\lvert\;{m}$ $\;$or $\;$ $p^n\;\lvert\;{m-1}$. For example $2^3\lvert\;m(m-1)$ then $2^3\;\lvert\;m$ ...
General Mathematics's user avatar
0 votes
1 answer
34 views

Does a infinite a.p with general modulus always contain a subsequence in which any 2 elements are coprime [closed]

Let $A=\{am_1+b, am_2+b, am_3+b,...\}$. for $a,b$ coprime integers, $a \gt 1$, and $m_i$ being a sequence of strictly increasing positive integers. Does $A$ always contain an infinite subsequence in ...
Antisocialfreal's user avatar
0 votes
1 answer
95 views

Divisibility of $a^m + b^m$ by $a^n + b^n$ implies divisibility of m by n [duplicate]

I'm working on a problem that states: Let $a, b, m, n$ be natural numbers, $a > 1$, and suppose that $a$ and $b$ have no common factors (GCD). We are asked to prove that if $a^m + b^m$ is divisible ...
AshishMath's user avatar
1 vote
1 answer
154 views

Understanding the motivation of a step in a proof

I need help understanding the proof of a divisibility problem I was trying, it is not that I do not understand the steps of the proof, but rather I'm having a hard time understanding the motivation of ...
Ruben's user avatar
  • 139
1 vote
0 answers
55 views

Confusion for algorithm for finding (a div d) and (a mod d), where a is an integer and d positive integer.

From Rosen's discrete Math textbook. I'm confused on 3 things regarding this algorithm (as can be seen via the screenshots) Why do we need an algorithm for finding $a$ div $d$ and $a$ mod $d$ when we ...
Bob Marley's user avatar
3 votes
2 answers
96 views

Determine the value of the sum of all elements of the set $A=\{ x \in \Bbb R | \frac{3x^2+5x+2}{x^2+x+1}\in \Bbb N\}$

The problem Determine the value of the sum of all elements of the set $A=\{ x\in \Bbb R : \frac{3x^2+5x+2}{x^2+x+1}\in \Bbb N\}$ my idea I wrote $3x^2+5x+2=(3x+2)(x+1)$ For $\frac{3x^2+5x+2}{x^2+x+1}$ ...
IONELA BUCIU's user avatar
4 votes
1 answer
136 views

2-adic valuations of $k\cdot 3^n-1$

I was just playing around with numbers of the form $3^n-1$, and noticed that their 2-adic valuations have a nice, understandable pattern: $\left(v_2(3^n-1)\right)_{n\ge 1} = (1,3,1,4,1,3,1,5,1,3,1,4,1,...
G Tony Jacobs's user avatar
1 vote
1 answer
90 views

When does $n$ divide $u_n$ if $u_1=1$, $u_n=(n-1)u_{n-1}+1$? [duplicate]

I'm working through the Background section to 'The Mathematical Olympiad Handbook' by A. Gardiner, OUP, 1997, and this appears on page 17: (***) Let $u_1=1$, $u_n=(n-1)u_{n-1}+1$. For which values of ...
John1970's user avatar
  • 441
5 votes
3 answers
211 views

Can $2^n = 111\ldots112?$ [duplicate]

I know that $2^n$ cannot $ = 1000\ldots002:$ because $3\mid 1000\ldots002$ but $3 \nmid\ 2^n.$ Also, $2^n$ cannot $ = 1111\ldots110:$ because $5\mid 1111\ldots110$ but $5 \nmid\ 2^n.$ Are there any ...
Adam Rubinson's user avatar
1 vote
2 answers
52 views

If $d\mid10a-1$ then $d\mid10q+r\iff d\mid q+ar$ [duplicate]

$d\mid10a-1$. Proof that then $d\mid10q+r$ if and only if $d\mid q+ar$ My attempt was to go once in this direction: $$d\mid10a-1 \wedge d\mid10q+r\implies d\mid q+ar$$ and then with this: $$d\mid10a-...
Piotr Wasilewicz's user avatar
2 votes
1 answer
127 views

Weird NT Question Related with Primes

Find the number of pairs of natural numbers $(k, p)$ with the following properties: 1)$p$ is a prime number 2)$k \leq 2p$ 3)$k^{p-1}|(p-1)^{k} +1$ 4)$k \neq 1$ Now i tried random stuff like: Case 1($p=...
CLASH ROYAL's user avatar
1 vote
0 answers
96 views

What $n$ would make $ \gcd _{k\ge1 }\left\{\dbinom{m+(k-1)\cdot n}{k}\right\}=1 \ \forall m \in \mathbb{N}$

This is a generalisation of this question. Construct the sequence $a_n$ $$ a_n = \begin{cases} 0, & \gcd _{k\ge1 }\left\{\dbinom{m+(k-1)\cdot n}{k}\right\}=1 \ \forall m \in \mathbb{N} \\ \min{m ...
pie's user avatar
  • 6,563
-4 votes
1 answer
51 views

Problem related to divisibility rules and digits [closed]

How do you prove that a 100-digit number that contains one hundred 0's, one hundred 1's, and one hundred 2's as its digits in a random order is not a perfect square? What about two hundred 0's, 1's, ...
Aarushi da Great's user avatar
-1 votes
2 answers
81 views

solution-verification | Show that the number $10^n+100^n+1000^n-3$ is divisible by 9, whatever $n$ is a natural number. [duplicate]

the problem Show that the number $10^n+100^n+1000^n-3$ is divisible by 9, whatever $n$ is a natural number. my solution if $n\geq 1$ First I wrote $10^n+ 10^{2n}+10^{3n}-3=10^n[1+10^n(1+10^n)]-3=100......
IONELA BUCIU's user avatar
1 vote
1 answer
111 views

Conjectures about the greatest common divisor of a vertical column of the pascal triangle.

I was playing around with pascal triangle I noticed an interesting property concerning the greatest common divisor $gcd$ of binomial coefficients along a vertical line. Specifically, the line ...
pie's user avatar
  • 6,563
0 votes
2 answers
57 views

Odd numbers and divisibility by $9999.....9999$ - an analysis. [duplicate]

I am currently interested in the problem For an integer $m$, define $f(m)$ as the smallest integer $n$ such that $m \ | \ \overbrace{9999\dots9999}^{n}$ This is a property I observed after messing ...
ducbadatchem's user avatar
4 votes
1 answer
122 views

On Prime, Lcm and Divisibility

Let $d_n= \text{lcm} \{1,2,3..., n \}$ then prove that for any prime $p$ $$ \left(\frac{1}{p^5-1}\right)\left(\frac{d_{p}}{p}\right)^5 \text{is not an integer}$$ Clearly $$\frac{d_p}{p}\in\mathbb{Z},...
Max's user avatar
  • 910
3 votes
1 answer
53 views

Prove that $2^𝑎 + 3$ is divisible by $2^{𝑎 + 𝑏} βˆ’ 9$ only if $𝑎 = 𝑏 = 2$

For $a$ and $b$ positive integers, I want to show that $2^π‘Ž + 3$ is divisible by $2^{π‘Ž + 𝑏} βˆ’ 9$ only if $π‘Ž = 𝑏 = 2$ and no other solutions exist. Note that I am only interested in the case ...
blu potatos's user avatar
2 votes
0 answers
19 views

Simple divisibility question [duplicate]

I want to find all $k$ such that for every pair of positive integers $(m, n)$, $(km + n) \mid{} (kn + m) \implies m \mid{} n$. Here are my ideas so far: Say that $(km + n) \mid{} (kn + m)$. Then ...
Christopher Miller's user avatar
4 votes
0 answers
163 views

Can we efficiently compute $a!\mod b$?

It is well known that we easily can compute , say , $2^a\mod b$ for large integers $a,b$. We can use the repeated square method which gives a fast result even if $a,b$ have , say , $50$ decimal digits....
Peter's user avatar
  • 85.1k
1 vote
0 answers
47 views

number theory, binomial coefficients divisibility

Let $p$ be a prime number greater than $3$ and $n$ a positive integer. Suppose $\nu _p(n) = r$. Prove that $\dbinom{np}{p} - n$ is divisible by $p^{3+r}$ The problem is here: https://poti.impa.br/...
amkpm90's user avatar
  • 352
2 votes
1 answer
102 views

Question on LCM and divisibility

Let $d_n= \text{lcm} \{1,2,3..., n \}$ then for which natural numbers $n$ is $$\frac{24 d_n^5}{(n+1)^5} \text{not an integer?}$$ We know that $$ \text{lcm}\{1,2,3,...,n\}.\text{gcd}\{1,2,3,...,n\}=n!$...
Max's user avatar
  • 910
0 votes
2 answers
37 views

Velleman 6.4.17 - Stuck with proof involving GCD and divisibility

Level and context: I'm a first-year undergraduate self-studying proof writing from Velleman's How to Prove It (second edition). Exercise 17 (a). Suppose $a$, $b$, and $p$ are positive integers and $p$ ...
NikWantsToLearnMaths's user avatar
0 votes
1 answer
66 views

Prove that $T_n=2^{2^n+1}+1$ is composite for $n \in \mathbb{N}$ [duplicate]

I was asked to prove for $n \in \mathbb{N}$ that $T_n=2^{2^n+1}+1$ is composite. One solution by induction is as follows: Base case $T_1$: $2^{2^n+1}+1=2^3+1=9=3^2$, so $T_1$ is composite with a ...
RobinSparrow's user avatar
  • 2,042
11 votes
2 answers
1k views

Is the product of all factors of an integer unique?

Given $n \in\mathbb{N}$ let $d$ the product of all the factors of $n$. Is $d$ unique to every $n$? I.e for $n\ne m$ can they have the same product of factors? It is easy to prove that $d$ is ...
Sersawy's user avatar
  • 345
1 vote
0 answers
28 views

Prove that, there exists infinite $n$ so that $n$ divides $2^n + 1$ [duplicate]

Let $n$ be a positive integer such that $n | 2^n+1$. Prove that, there are infinite solutions My attempt: My intuition was to show that $n=3^k$ for any positive integer $k$ works, which I tried to do ...
cyroah's user avatar
  • 21
0 votes
3 answers
95 views

$a \mid p^i b\,$ and $\, b \mid p^j a\, \Rightarrow\, a \mid b \,$ or $\, b \mid a,\,$ for any prime $p$

I would like to prove the following implication: Given any prime $p$, we have $$ a \mid p b \land b \mid p a \implies a \mid b \lor b \mid a $$ I am on a path to proving the prime decomposition ...
Léreau's user avatar
  • 3,123
2 votes
0 answers
71 views

I do not understand how we got this inequality in this solution

So this is the problem and solution. I have question about presented solution itself, problem is from 1998 Romanian IMO Team Selection Test if that would be any help, question at the end. Problem: ...
Saba's user avatar
  • 21
2 votes
1 answer
61 views

Determine whether the following statement about prime factors of $2^n+1$ is true or false:

There are infinitely many prime numbers $p$,$\enspace$s.t.$\enspace p$ doesn't divide $2^n+1$ holds for all $n\in\mathbb{N}_+.$ My view is that the set $\lbrace 2^n+1\vert n\in\mathbb{N}_+\rbrace$ ...
Lonely patients's user avatar
0 votes
0 answers
51 views

Let m be an integer greater than 2, prove that for any positive integer n, $2^n+1$ is not divisible by $2^m-1$ [duplicate]

The answer uses proof by contradiction by assuming a minimum n and proving that n-m also satisfies, but I don't really know the thinking process behind this construction. Are there any hidden ...
electronic's user avatar
0 votes
3 answers
134 views

Is $2^{2+4n}+1$ divisible by $5$? [duplicate]

I have a question from a pattern that I noticed in numbers of the form: $$I_n=2^{2+4n}+1$$ for $n\geq0$. All $I_n$ numbers up to $n=7$ seem to show $5\mid I_n$. But is this the case for any arbitrary $...
Simón Flavio Ibañez's user avatar
2 votes
0 answers
76 views

Is the greatest prime factor of $2^n+1$ greater than or equal to $n$. [duplicate]

I had this question because I had to prove for a problem that $2^n+1 \not \mid (n-1)!$, so I thought it would be nice for there to be a prime factor of $2^n+1$ that is greater than $n-1$. I checked ...
Semicolumn's user avatar
0 votes
0 answers
20 views

For a given $m$, which is relatively prime to $p$, show there exists an $r$ such that $m$ divides $p^r-1.$ [duplicate]

My question is: Suppose that we have an arbitrary natural number $m$ that is not divisible by the prime number $p.$ Then there exists an integer $r$ such that $m$ divides $p^r-1$. Some help on this ...
ikey's user avatar
  • 133
3 votes
2 answers
116 views

Find all positive integers $a$ and $b$ such that $a^4-21a^2b^2+4b^4$ is a divisor of $3^3\cdot7^2\cdot19$

Find all positive integers $a$ and $b$ so that $a^4-21a^2b^2+4b^4$ is a divisor of $25137$. I am stuck with this math problem. I know that: $$a^4-21a^2b^2+4b^4=(a^2+2b^2-5ab)(a^2+2b^2+5ab)$$ and $$...
LE Thai-Hung's user avatar
2 votes
1 answer
60 views

What property a ring extension of UFDs $R\subseteq S$ must have, such that for $a,b\in R$, $a | b$ in $S \implies a | b$ in $R$?

Let $R,S$ be two UFDs, and $R \subseteq S$, a ring extension with the following property (P) $$(\forall a,b\in R) (\ a|b \ in \ S \longrightarrow a|b \ in \ R).$$ Question: What are some conditions ...
Cezar's user avatar
  • 147
0 votes
0 answers
26 views

Find the largest integer $x$ such that $x - 6 | x^{1000} + 2$. [duplicate]

Find the largest integer $x$ such that $x - 6 | x^{1000} + 2$. How would I go about solving for $x$? I am told that the answer should have just under 800 digits, so brute forcing is not possible. I ...
Karl Stolze's user avatar
0 votes
0 answers
18 views

If $d_1,\cdots,d_k$ are all the positive divisors of $n\in\mathbb{N}$ in increasing order, then $d_i d_{k+1-i}=n$ for all $i=1,\cdots,k$ [duplicate]

I'm trying to proof that I can "pair" the divisors of a given natural number. If we pick $d_i$, by definition there exists $q\in\mathbb{N}$ such that $n=d_i q$, therefore $q$ is also a ...
isaac098's user avatar
0 votes
2 answers
72 views

i am having trouble with understanding a number theory question's answer

I am new to number theory and I am having trouble understanding this https://math.stackexchange.com/a/456130/1311304 solution. I don't understand how $2^{a-b}+1$ is divisible by $2^b-1$ proves that $a&...
Toshiv's user avatar
  • 21
2 votes
1 answer
181 views

Let $x,y,z$ are selected from set of natural numbers. Find the probability that $x^2+y^2+z^2$ is divisible by $5$

Let $x,y,z$ are selected from set of natural numbers. Find the probability that $x^2+y^2+z^2$ is divisible by $5$ My Method: I took set of first $10$ natural numbers. Let say set is $S=\{1,2,3,...,10\...
mathophile's user avatar
  • 3,845
0 votes
1 answer
37 views

If $p$ is prime number what are his predecessor and successor $p-1$ and $p+1$ [duplicate]

I suppose that $p-1$ is even number and that $p+1$ is divisible by 3 or vica versa. My first problem is that I needed to prove that $p^2 -q^2$ is always divisible by 24 for $p,q$ being prime numbers ...
Stephanie V's user avatar
4 votes
3 answers
184 views

Determine the pairs $(x,y)$ of integers satisfying $2x^2-3xy+y+1=0$.

the question Determine the pairs $(x,y)$ of integers with the propriety that $$2x^2-3xy+y+1=0$$ my idea I tried writing it as a product of terms but got to nothing useful. Then I applied the quadric ...
IONELA BUCIU's user avatar
3 votes
0 answers
32 views

Does a set with no divisibility pairs necessarily have arbitrarily large gaps? [duplicate]

The set of prime numbers has the following properties: No element is divisible by any other element. We can find arbitrarily large gaps between consecutive elements. Does (1) imply (2) for arbitrary ...
Karl's user avatar
  • 11.8k
2 votes
1 answer
87 views

Finding the 123ʳᡈ Number in a Sequence After Removing Multiples of 5 or 7

I'm working on a problem involving a sequence of the first 300 positive integers, from 1 to 300. However, I need to find the 123ʳᡈ number in the sequence after removing all numbers that are divisible ...
My Car's user avatar
  • 152
2 votes
0 answers
79 views

Proof of a "Fermat Last Theorem" subcase

Let us consider the equation $x^p + y^p -z^p = 0$, where $p$ is some prime number and $x,y,z$ are positive, pairwise coprime, integers. By Fermat's Little Theorem, we have that $$x^p \equiv x \space (\...
Juan Moreno's user avatar
  • 1,190
0 votes
0 answers
38 views

Divisibility (algebraic expressions) - can this be generalised?

Consider the expression $a^{3}+b^{3}+c^{3}-3abc$. It is divisible by $(a+b+c)$ Now, consider the expression $a^{3}+b^{3}+c^{3}+d^{3}-3(abc+abd+acd+bcd)$ It is divisible by $(a+b+c+d)$ Can this be ...
Red Five's user avatar
  • 2,807
1 vote
1 answer
110 views

Casting out nines and digital sums for fractions (rationals) [closed]

I am a high school student and there is something I want to ask about the application of digital sums. Let's say there is a fraction "520/7", let 520/7=a, so 520= a Γ— 7, so if we now ...
Shyam's user avatar
  • 49
0 votes
1 answer
43 views

Bound of squarefree part of an integer

I am studying the paper DIOPHANTINE EQUATIONS OF THE FORM $F(X) = G(Y)$ - AN EXPOSITION which discusses the result of Erdos and Selfridge. I am unable to understand the highlighted statement ''Clearly ...
SARTHAK GUPTA's user avatar
6 votes
1 answer
386 views

37 and Veritasium

In Veritasium's new video about 37 there is brought up something interesting about its multiples. For any multiple of 37 reverse it and put a 0 between all of its digits and the new number will be a ...
ShrekLover's user avatar
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 ...
Juan Moreno's user avatar
  • 1,190
3 votes
1 answer
227 views

Can this divisibility be proven in general?

Let $n$ be a positive integer with $n\equiv 4\mod 6$ and define $p:=\frac{n^2+n+1}{3}$ (which is in this case a positive integer as well). Conjecture : $$p^2\mid n^n+(n+1)^{n+1}$$ for every $n$ of ...
Peter's user avatar
  • 85.1k

1
2 3 4 5
…
125