Questions tagged [divisibility]
This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.
2
votes
3answers
61 views
Why does the statement “p is prime if it is divisible by only itself and 1” define only one prime number?
I'm having a bit of trouble understanding why this incorrect definition of primality only defines one prime number.
"p is prime if it is divisible by only itself and 1."
My understood definition of ...
-1
votes
4answers
88 views
Help to prove: $2^{(n+1)}+ 3^n+ 5^n$ is divisible by $6$ [on hold]
The question asks to use mathematical language to prove that:
$2^{(n+1)}+ 3^n+ 5^n$ is divisible by $6$.
such that n is any positive integer.
-1
votes
3answers
44 views
Can $ab+cd$ be an integer if $a, b, c, d$ are non integers and each 3 sum to an integer [on hold]
Can $ab+cd$ be an integer if $a, b, c, d$ are non integers and each 3 sum to an integer.
This question in my opinion is tricky and I am unable to do much in it. However, after trying to substitute I ...
0
votes
0answers
27 views
Prove that $(a^2b^2)^k + (b^2c^2)^k + (c^2a^2)^k$ is divisible for $\dfrac{1}{2}(a^4 + b^4 + c^4)$.
If $a$, $b$ and $c$ are a Pythagorean triple then prove that $(a^2b^2)^k + (b^2c^2)^k + (c^2a^2)^k$ is divisible for $\dfrac{1}{2}(a^4 + b^4 + c^4)$ for all integer $k \ge 2$.
I cannot think of any ...
0
votes
2answers
87 views
A problem of divisibility [on hold]
Say $n$ is a natural number such that $$3^n+3^{n+1}+...+3^{2n}=k^2$$ where $k$ is a natural number. Prove that $n$ is divisible by $4$.
4
votes
2answers
59 views
Show that $m\mathbb{Z}$ is a subgroup of $n\mathbb{Z} \iff m|n $
Show that $m\mathbb{Z}$ is a subgroup of $n\mathbb{Z} \iff n|m $
I think my solution for one way of this is correct:
$\Rightarrow$ Suppose $m \mathbb{Z}$ is a subgroup of $n\mathbb{Z}$
, then $m \...
3
votes
6answers
70 views
Prove without induction that $2×7^n+3×5^n-5$ is divisible by $24$.
I proved this by induction. But I want to show it using modular arithmetic. I tried for sometime as follows
$$2×7^n-2+3×5^n-3\\
2(7^n-1)+3(5^n-1)\\
2×6a+3×4b\\
12(a+b)$$
In this way I just proved ...
0
votes
0answers
16 views
N has all divisors up to 31 except two
Let $N$ be a positive integer. It is true that $1|N, 2|N, 3|N, \dots, 31|N$, except two. Which are false?
It seems like the problem is impossible. For example, any two consecutive integers must have ...
0
votes
1answer
37 views
Is $\binom{2^{n}}{j}\cdot 2^{2^{n}-j}$ divisible by $2^{n}$ for all $0 \leq j < 2^{n}$?
This is immediate for $j \leq 2^{n}-n$. I also know that $0 \equiv 3^{2^{n}} - 1 = \sum_{j=0}^{2^{n}-1} \binom{2^{n}}{j}\cdot 2^{2^{n}-j} \mod{2^{n}}$. Induction does not seem to help. Any hints or ...
-2
votes
1answer
41 views
Number System Divisibility by 7
X is a number formed by writing 9 for 99 times. What will be the remainder of this number when divided by 7?
2
votes
2answers
96 views
Suppose that $T$ is the smallest positive integer satisfying $m^{T}\equiv \pmod {pq}$. Prove that $T\mid(p-1)(q-1)$.
Suppose that $p$ and $q$ are distinct primes and that $m$ is an integer satisfying $\gcd(m, pq) = 1$. Suppose that $T$ is the smallest positive integer satisfying $m^{T}\equiv \pmod {pq}$. Prove ...
1
vote
2answers
247 views
Prove that there exist $135$ consecutive positive integers so that the $n$th least is divisible by a perfect $n$th power greater than $1$
Prove that there exist 135 consecutive positive integers so that the second least is divisible by a perfect square $> 1$, the third least is divisible by a perfect cube $> 1$, the ...
1
vote
1answer
51 views
What are the necessary conditions for a polynomial Q(X) such that the roots of Q(X) - X are equal to the real roots of a polynomial P?
If $P(X), Q(X) ∈ ℝ[X]$ , and $P(X) | P( Q(X) ) $ , what could be the necessary conditions for $Q(X)$ such that the set of the real roots of $P(X) $ to be equal to the set of the real roots of $Q(X) - ...
0
votes
2answers
39 views
Prove that the sum is not an integer
Prove that if a / b and c / d are two irreducible rational numbers such that gcd (b, d) = 1 then the sum (a/b + c/d) is not an integer.
I was thinking about the proof by contradiction, but then I ...
2
votes
6answers
66 views
If $d$ divides $2n$ and $d$ doesn't divide $n$, then $d$ is even
I have encountered a proof regarding dihedral groups we this fact is used:
If $d\mid 2n$ and $d\nmid n$, then $d$ is even and ${d\over 2}\mid n$.
I can't seem to understand why this is true. If $d\...
0
votes
2answers
60 views
$a$, $b$, and $c$, non-negative consecutive integers with $a + b + c$ odd, prove $abc$ divisible by $24$ [duplicate]
If $a$, $b$, and $c$ are three non-negative consecutive integers and $a + b + c$ can't be divided by $2$.
Prove by induction that $abc$ can be divided by $24$.
For the question I don't even know ...
4
votes
1answer
33 views
Testing polynomial divisibility by evaluation at specific points
This question is just something I got to wondering about. Assume
$$p(x), q(x) \in \Bbb Z[x], \deg (q) = m \lt \deg(p) =n.$$
Assume also $\forall a_k \in \{a_k~|~0 \leq k \leq n-m \} \subseteq \Bbb ...
4
votes
1answer
39 views
How many five digit numbers formed from digits $1,2,3,4,5$ (used exactly once) are divisible by $12$?
How many five digit numbers formed from digits $1,2,3,4,5$ (used exactly once) are divisible by $12$?
My answer is $24$ but I doubt if it's right or not.
Sum of all the digits is $15$, so all the ...
2
votes
3answers
66 views
Is there a positive integer $n$ where $14$ divide $30^n$? Explain why.
The lecturer has not taught us proofs yet, so I think the question is not looking for a rigorous proof. My attempt:
$$30 = 2 \times 3 \times 5$$
$$\frac{30^n}{14} = \frac{2^n \times 3^n \times 5^n}{2 ...
2
votes
1answer
85 views
How to elegantly find the remainder of $en$ divided by $n+1+\frac{n-1}{d}$
Motivation:
Let $n,e,d$ be positive integers greater than 2, such that $e\mid n-1$ and $d\mid n-1$. Denote $N=en$, $M=n+1+\frac{n-1}{d}$. Find $q,r\in \mathbb{Z}$
such that $$N=qM+r, 0\le r < ...
0
votes
2answers
46 views
Exercise on polynomial and GCD
Let $f(x), g(x)$ be relatively prime polynomial with coefficients in $\mathbb{Z}$. How can I prove that the GCD $(f(n),g(n)) = O(1)$ for $n \to \infty$, $n \in \mathbb{N}$?
Thank you for the help!!
0
votes
1answer
20 views
For positive integers prove that $a\Big|bc \implies a\Big|b \lor a\Big|c$
$a\Big | b,\; b = ak.$ $a\Big|c, c = al,$
So do I multiply $b$ and $c$ to get $a(kl)$ to prove that $bc = a$ multiplied by some integer $kl$ closed under multiplication?
-2
votes
1answer
36 views
prove: if $ab\mid cd$ and $a\mid c$ and $ab\nmid c$ then $b\mid d$ [closed]
I'm having a hard time proving the following claim:
if $ab\mid cd$ and $a\mid c$ and $ab\nmid c$ then $b\mid d$
Any help would be appreciated
9
votes
1answer
196 views
A006517: Numbers with $n\mid 2^n+2$
Problem 323 from the IMO 2009 reads:
Prove that there are infinitely many positive integers n such that $2^n+2$ is divisible by $n$.
An amazingly nice (and short) solution can be found here (see ...
0
votes
0answers
34 views
Modular Arithmetic with Negative Exponents
In one proof I'm trying to figure out, I've arrived at a part where I am thinking about whether $x≡1$ and $y≡1$ imply $x^ay^b≡1$ for any real integers a and b. I know that in general, if $u≡v$ and $c≡...
1
vote
2answers
66 views
Is $n^2+3n+6$ divisible by 25, where $n$ is a integer?
If we want $n^2+3n+6$ to be divisible by $25$, it firstly has to be divisible by $5$.
So, let's take a look at couple of cases:
$n=5k: 25k^2+15k+6$. The remainder is $6$, so it's not divisible by $25$....
2
votes
1answer
36 views
How to divide by decimal quickly?
My friend asked me to help solve a problem in which she cannot use a calculator.
$$
\require{enclose}
\begin{array}{r}
32.45 \enclose{longdiv}{253.11} \\[-3pt]
\end{array}
$$
What is the best method ...
0
votes
3answers
83 views
Prove or disprove: if $10$ divides $n^{4}$, then $10$ divides $n$
I want to prove or disprove that for a natural number $n$, if $10|n^4$, then $10|n$. I'm really struggling to decide on how to comprehensively prove it or not, because all of the other related ...
0
votes
1answer
51 views
Dividers of a number
I found this function, and i have problems with the demonstration of truth or falseness of this afirmation, so some one can help me?
Let S and P be the sum and the product of the divisors of a number ...
1
vote
3answers
280 views
Finding integer solution to a quadratic equation in two unknowns [closed]
We have an equation:
$$m^2 = n^2 + m + n + 2018.$$
Find all integer pairs $(m,n)$ satisfying this equation.
0
votes
0answers
36 views
Base $b$ such that as many $x_b$ divide $x$ in set $\mathcal{Q}$
Assume $d|n$ means that integer $d$ divides integer $n$. Define
$\chi^k$ to be the $k$-th element in a set. Consider the set
$\mathcal{Q} =\{1, 2, 3, \dots, 2019\}$. For a base $b$ such that
$1&...
3
votes
1answer
79 views
Show that $a^n-b^n$ has a prime factor which does not divide $a-b$ for all $n>1$ .
I was asked to prove the following using the lifting the exponent lemma.
Show that $a^n-b^n$ has a prime factor which does not divide $a-b$ for all $n>1$ .
Using the first lemma, what I ...
0
votes
1answer
21 views
Checking Proof for the following Divisibility
Prove that for every natural number $n\ge 2$, $n$ does not divide
$n+1$.
Proof: Suppose for every natural number $n\ge 2$, $n$ does divide $n+1.$ However, for natural numbers $a$ and $b,$ $a$ ...
1
vote
1answer
36 views
Showing that, for $c,d\in\Bbb N$, $c|d$ implies $c\leq d$
I need help solving the following. My idea is to use Euclid's algorithm however I was told that I can simply prove this just with natural numbers.
Prove that for all natural numbers $c$ and $d$, ...
3
votes
3answers
74 views
number of solutions of $x^2=x$ divides the number of invertible elements in a ring
Let $A$ be a commutative ring with odd number of elements. If $n$ is the number of solutions of the equation $x^2=x,x\in A$, and $m$ is the number of invertible elements of $A$, prove that $n$ divides ...
0
votes
1answer
40 views
Show that if $n$ and $k$ are positive integers, then $\lceil \frac{n}{k} \rceil = \lfloor \frac{n-1}{k} \rfloor + 1$
This is expanding on this question: Show that if $n$ and $k$ are positive integers, then $\lceil \frac{n}{k} \rceil = \lfloor \frac{n - 1}{k} \rfloor + 1$ as I'm unclear on how to solve this statement....
9
votes
1answer
110 views
Sum of squared arctangents
I discovered a curious identity
$$\small{2939\arctan^2 2+450\arctan^2 8+84\arctan^2 13+330\arctan^2 18+147\arctan^2 38=\\1250\arctan^2 3+252\arctan^2 4+360\arctan^2 5+870\arctan^2 7+210\arctan^2 21+...
0
votes
2answers
44 views
Can $p(x)\in \mathbb{F}_{3}(x)$ with $p(x)=\frac{x²+x+1}{x+1}$ be expressed as a polynomial? Is it not possible for any of the given fields?
Can $p(x)\in \mathbb{F}_{3}(x)$ with $p(x)=\frac{x²+x+1}{x+1}$ be expressed as a polynomial?
I tried it with different steps, like with polynomial long division:
$ (x^2 +x +1):(x+1)=x + \frac{1}{x+1}...
3
votes
4answers
76 views
Proving $3\mid p^3 \implies 3\mid p$
I want to prove $3\mid p^3 \implies 3\mid p$ (Does it?)
The contrapositive would be $3 \nmid p \implies 3 \nmid p^3$ I believe.
$3\nmid p \implies p = 3q + r$ ($0<r<3$), so $p^3 = 27q^3+27q^2r+...
-3
votes
3answers
139 views
How to prove that 2017 divides $1^{2017}+2^{2017}+\dots+2017^{2017}$?
How can I prove that $2017 \mid 1^{2017}+2^{2017}+\dots+2017^{2017}$?
I tried proving it with the use of modulo, however it was to no avail. Afterwards, I tried researching, for possible theorems, ...
10
votes
1answer
132 views
Prove that $16 ^ {2023} + 1$ is divisible by $17 ^ 2$.
Prove that $16 ^ {2023} + 1$ is divisible by $17 ^ 2$.
It is clear that $16 ^ {2023} + 1$ is divisible by $17$, but why it is divisible by $17 ^ 2$ is not clear.
2
votes
1answer
67 views
A ten digit number formed without repetition using numbers $0$ to $9$ is divisible by $11111$. Find the greatest and smallest such number.
A ten digit number is formed by using the numbers between $0$ and $9$ without repetition. If the number formed is divisible by $11111$. Find the greatest and smallest such number.
I tried very hard ...
1
vote
6answers
54 views
If $\gcd(n,18)=3$ then $\gcd(n^2,18)=9$
Rest of the problem is fairly obvious. If $\gcd(n,18)=3$ then $3$ divides $n$ so there exists $a$ such that $3a=n$. Squaring both sides gets us $9a^2=n^2$ so we get $9 \mid n^2$. Obviously $9$ divides ...
0
votes
1answer
51 views
Recursive Induction Problem
Define a sequence ($a_i$) i∈ Natural Numbers, recursively by $a_1 = 3, a_2 = −6$, and, for all $ n ≥ 2,\; a_{n+1} = a_n + 2a_{n−1} + 3.$ Prove $3$|$a_n$ for all $n ∈ \mathbb N$.
I have tried this ...
1
vote
1answer
34 views
Adding sum of leftmost digits
Starting with a number of at least $9$ digits, every minute we add the sum of the leftmost $9$ digits of the current number to the number itself. Will we always, at some point, see $9$ consecutive ...
0
votes
0answers
26 views
Find $GCD(2^{120}-1,2^{100}-1)$ [duplicate]
Find $GCD(2^{120}-1,2^{100}-1)$. ($GCD$ means greatest common divisor)
2
votes
2answers
50 views
Finding out the remainder of $\frac{11^\text{10}-1}{100}$ using modulus [duplicate]
If $11^\text{10}-1$ is divided by $100$, then solve for '$x$' of the below term $$11^\text{10}-1 = x \pmod{100}$$
Whatever I tried:
$11^\text{2} \equiv 21 \pmod{100}$.....(1)
$(11^\text{2})^\text{2}...
5
votes
6answers
84 views
Find the smallest $n \ge 1000$ such the sum $ 1+11+111+⋯+11⋯11 (n$ digits) is divisible by $101$
I get another training problem, for a Romanian 6th grader competition, for which I have no answer.
Find the smallest $n \ge 1000$ such the sum $ 1+11+111+⋯+11⋯11 (n digits)$ it is divisible by 101. I ...
0
votes
2answers
21 views
Remainders of two integers when divided by another integer n
I am curious if the remainder of u+v is the same as the sum of the two integers separately if they are the same how would one go about proving this
0
votes
1answer
36 views
How do I calculate the number of pairs/quadruples in an array such that their sum is divisible by '3'?
How do I calculate the number of pairs/quadruples in an array such that their sum is divisible by '3' ?
I know the brute force approach, I am looking for a much optimized solution :-)
I have solved ...
