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.

2
votes
1answer
59 views

Divisibility of $x^2+y^2$ by prime $p$

I've read the following fact on my number theory textbook, there's no proof on the book of such result, I tried working it out on my own but I'm kinda lost, the lemma is the following: Given two ...
-1
votes
0answers
9 views

How can the facial thirds be measured without reference points? [on hold]

So I have an interesting question regarding facial thirds. My concern is about how a quantifiable base of the sum of all three thirds divided can be reliably accurate insofar as to properly measure ...
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 ...
1
vote
1answer
38 views

Does there exist a composite, deficient, odd number that is divisible by the sum of its proper factors?

Consider $n \in \mathbb{N}$. Define the aliquot sum function $s(n)$ to be the sum of the proper divisors of $n$ (the divisors not including $n$ itself). Call $n$ deficient if $s(n) < n$, abundant ...
2
votes
1answer
74 views

A problem regarding polynomials $x^t+1$ [on hold]

For what value of $t$ is $x^t+1$ divisible by $x^{15}+x^{14}+1$. How to find it?
5
votes
1answer
62 views

Two friends have $2$ natural written on their forehead. One is $2$ times the other + $1$. They can raise their hands.

The problem: Two friends have $2$ natural written on their forehead. One of them is $2$ times the other + $1$. Let's call them $X$ and $2X + 1$. They have to come up with a strategy to guess their ...
6
votes
2answers
101 views

Show that $(\binom{p^2}{p} -p ) $ is divisible by $p^5$, for every prime number $p, p\ge 5$

Show that $(\binom{p^2}{p} -p ) $ is divisible by $p^5$, for every prime number $p, p\ge 5$. I have a combinatorics problem, and this is what it reduces to. I am not quite sure how to link the fifth ...
-1
votes
2answers
33 views

Divisibility Theory [on hold]

The question asks me to prove that no integer of the $8k+5$ where k is a positive integer, can ever be a perfect square.
0
votes
1answer
7 views

Return the number of integers within the range of a and b that are divisible by x

So I have a question here: Return the number of integers within the range of a and b that are divisible by x. So I have, a = 0, b = 17 and x = 17. Apparently the answer is 2. I understand that 17 /...
0
votes
1answer
53 views

Number of divisors of $ 20^{20} $ with exactly $20$ divisors

How many positive integers $x$ with $x\mid 20^{20}$ have exactly $20$ divisors ?
3
votes
4answers
136 views
+50

A simple doubt in number theory problem.

I considered an even number $n\geq 10$, where it is divisible by some positive integer $k$. Also, $k$ divides $\frac{n}{2}$. Then $n = kq\implies k\cdot\frac{q}{2} = \frac{n}{2}$. Can we say that $q$...
0
votes
0answers
51 views

If $y^2-x^2\bigm|2^ky-1$ and $2^k-1\bigm|y-1$ then $y=2^k$ and $x=1$

Suppose that $k\geq2$ and $0<x<y$ and $y^2-x^2\bigm|2^ky-1$ and $2^k-1\bigm|y-1$. Is it necessarily the case that $x=1$ and $y=2^k$? I've tested this up to $k\leq50$ and $y\leq10000$ but I ...
2
votes
4answers
76 views

Find all pairs $(m, n)$ of positive integers such that $m$ divides $8n+1$ and $n$ divides $8m+1$

I've found the pairs $(1,3),(1,9),(3,25)$ and $(13,21)$ up to order. But I have no idea how to prove that there are not other solutions. Any hints...? I've been trying for a few days but all I came up ...
3
votes
1answer
123 views

Are are infinitely many intimate pairs of integers?

Using the standard statistical definitions, the variance of $x_1, x_2, \ldots, x_n$ and the squared errors about its mean $\mu$ are given by $\sigma^2 = \sum_i(x_i - \mu)^2/n$ and $\delta_2 = \sum_i(...
1
vote
1answer
25 views

Determine a property of $S_b(n)$, which is the sum of the digits of $n$ when $n$ is expressed in base $b$

The original question Let $S_b(n)$ be the sum of the digits of $n$ when $n$ is expressed in base $b$. was asked by Anson Chan on Jan. 24, 2019. Since it was deemed to not have enough context, it was ...
2
votes
2answers
80 views

Proof for divisibility of polynomials. [closed]

I have no idea how to proceed with the following question. Please help! "Prove that for any polynomial $ P(x) $ with real coefficients, other than polynomial $x$, the polynomial $ P(P(P(x))) − x $ is ...
2
votes
3answers
41 views

Prove $a^n+1$ is divisible by $a + 1$ if $n$ is odd [duplicate]

Prove $a^n+1$ is divisible by $a + 1$ if $n$ is odd: We know $a$ cannot be $-1$ and the $n \in \mathbb{N}$. Since $n$ must be odd, we can rewrite $n$ as $2k+1$. Now we assume it holds for prove that ...
1
vote
0answers
34 views

A mysterious fact related to digital root of a 'special incorrect division' and 'correct division'.Whats the reason behind it?

I observed that the digital root of an 'incorrect division' obtained by dividing a number in a 'special way'/'particular manner' and the digital root of the correct division are always same. The ...
5
votes
3answers
87 views

$8^n-3^n$ Divisible by 5 - Proof Verification.

Statement: $\frac{8^k-3^k}{5}=M, M\in\mathbb{N}$ Base case: $P(1): \frac{8-3}{5}=1\in\mathbb{N}$ Assume $P(n): \frac{8^n-3^n}{5}=N$ Then, $P(n+1)=8^{n+1}-3^{n+1}=5K$, where $K$ is in terms of $M$ ...
0
votes
1answer
21 views

Given a number $N$ and two numbers lower than $N$, what are all of the combinations of those numbers that sum to $N$?

I tried looking around the website for a while but I was unable to find anything that matched this problems specifically. So if someone here knows of a question that is the same as mine, please link ...
2
votes
3answers
242 views

Can divisibility rules for digits be generalized to sum of digits

Suppose that we are given a two digit number $AB$, where $A$ and $B$ represents the digits, i.e 21 would be A=2 , B=1. I wish to prove that the sum of $AB$ and $BA$ is always divisible by $11$. My ...
1
vote
1answer
33 views

Prove that if x is odd and y is even, then gcd(x+y,x-y)=gcd(x,y)

It is trivial to prove that gcd(x,y) divides gcd(x+y,x-y). How is it possible to prove gcd(x+y,x-y) divides gcd(x,y)? I don´t know how to use the fact that x is odd and y is even. Can anybody help me ...
2
votes
1answer
34 views

If $a \mid c$ and $b \mid c$ where $a, b, c \in \mathbb{N}$, under what conditions does it follow that $a \mid b$?

The following question is pretty basic, and the underlying idea was used in the "proof" of a statement in this hyperlinked answer to another MSE question. The question is as follows: If $a \mid c$ ...
1
vote
6answers
102 views

$31$ divides to $28!+233$? [duplicate]

How to prove that $31$ divides to $28!+233$? I have tried to use Wilson's theorem and the primes decomposition theorem but I have not had success. Thanks for your help
0
votes
2answers
32 views

Does division by zero imply a different type of division in this situation

Firstly, I would like to apologize if this is somehow addressed in one of the many many explanations about why division by 0 is impossible that appear on this site. I have not yet found one that ...
1
vote
2answers
45 views

Number theory divisibility check question

N = $2^{744} - 1$. Prove N is divisible by $2^{93}+2^{47}+1$. I have no idea how to proceed. (edit: removed first part as I got the answer)
1
vote
1answer
31 views

Is there a name for the largest factor $f$ of a number $n$ so that $n/f \ge f$?

TL;DR: Is there a name for the largest value of $f$ for which $f|n$ and $n/f \ge f$? Or a name for the smallest value of $f$ for which $f|n$ and $n/f < f$? Additional clarification. This question ...
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) = \...
1
vote
1answer
60 views

Find all triplets $(a,b,c)$ less than or equal to 50 such that $a + b +c$ be divisible by $a$ and $b$ and $c$.

Find all triplets $(a,b,c)$ less than or equal to 50 such that $a + b +c$ be divisible by $a$ and $b$ and $c$.(i.e $a|a+b+c~~,~~b|a+b+c~~,~~c|a+b+c$) for example $(10,20,30)$ is a good triplet. ($10|...
1
vote
3answers
94 views

Find the remainder when the polynomial $1+x^2+x^4+x^6+…+x^{22}$ is divided by $1+x+x^2+x^3+…+x^{11}$

Find the remainder when the polynomial $$1+x^2+x^4+x^6+....+x^{22}$$ is divided by $$1+x+x^2+x^3+...+x^{11}$$ $1+x^2+x^4+x^6+....+x^{22}=\frac{x^{24}-1}{x^2-1}$ $1+x+x^2+x^3+...+x^{11}=\frac{x^{12}-...
0
votes
2answers
56 views

Prove that if $f(x)$ divides $g(x)$ and $f(x)$ divides $h(x)$, then $f(x)$ divides $s(x)g(x) +t(x)h(x)$.

Let $F$ be a field. Prove that for all polynomials $f(x), g(x), h(x) \in {F}[x]$, if $f(x)$ divides $g(x)$ and $f(x)$ divides $h(x)$, then for all polynomials $s(x), t(x)\in {F}[x]$, $f(x)$ divides $s(...
0
votes
0answers
40 views

Non-trivial divisors

I want to find out the number of integers whose biggest non-trivial divisor is exactly $k$ times the smallest non-trivial divisor of that integer. My thoughts are, that the smallest divisor $n$ has ...
3
votes
3answers
47 views

How to eliminate prime factors from algebraic integers?

I'm trying to eliminate prime factors from algebraic integers. Is the following true without further restrictions? And how can I prove it? Let $p,N,M\in\mathbb Z$, let $p$ be prime such that $gcd(p;N)...
-3
votes
0answers
98 views

Nice tuples! A number theory problem. [duplicate]

How many tuples $(a,b,c)$ could be found so that $a+b+c$ is divisible by $a$ and $b$ and $c$. $a, b, c\; $ are natural numbers less than or equal to $50$. I'm stuck on this homework problem. ...
1
vote
1answer
45 views

Divisibility of fourths by seven

I am otherwise very good in mathematics, but recently I came upon a problem that I just can't solve. Do you have any idea how to solve it? If $a^2 + b^2 + c^2$ is divisible by 7, prove that $a^4 + b^...
1
vote
2answers
106 views

Prove that $\frac{(72!)}{(36!)^2}-1$ is divisible by 73 [closed]

Prove that $\frac{(72!)}{(36!)^2}-1$ is divisible by 73. My approach is as follow $73n=\frac{(72!)}{(36!)^2}-1$ I tried remainder theorem but could not prove it.
1
vote
2answers
27 views

Prove that $M_n\mid (i+n)(i-n)$ and $M_n\mid(i+n-1)(i-n+1)$

My friend gave me a problem: Prove that if $M_n$ is the $n^\text{th}$ odd number, then for all integers $i$, $$M_n\mid (i+n)(i-n)\quad\text{and}\quad M_n\mid(i+n-1)(i-n+1)\tag*{$[1]$}$$ The ...
0
votes
1answer
59 views

How l can draw Hasse diagram

How can l draw a Hasse diagram of the divisibility relation, when $$B=\{2,4,5,6,7,10,18,20,24,25\}$$ Would any help, thank you.
1
vote
2answers
50 views

How to determine the smallest value of $N=n^4+6n^3+11n^2+6n$ if 13 and 19 both divide N?

I tried to solve for an integer solution by making N equal to multiples of 247 but this is not leading me anywhere. I then tried using the tests for divisibility which did not seem to lead me anywhere ...
2
votes
3answers
103 views

Hopeless Numbers

Beatriz Viterbo has called a positive integer which is not divisible by any of the ($2^n$, where $n$ is the number of its digits) numbers that result by introducing a plus or minus sign to the left of ...
0
votes
1answer
15 views

distribute items into containers evenly without splitting

Im trying to figure out how to place a number of items into containers evenly but without splitting. Easy example: 11 items, 2 containers 11/2 = 5.5 so even distribution would look like this (...
4
votes
3answers
153 views

Isn't there any divisor $k$ of $n^4$ such that $n^2-n<k<n^2$?

I did some experiment with my Python script to find a number which could divide $n^4$ in this interval ($n^2-n$, $n^2$). I watched the form of prim factors of the numbers in this ($n^2-n$, $n^2$) ...
1
vote
7answers
81 views

How to find divisibility of a very large number

I was asked this question in a test: The number $111111...111$ ($1$ comes 91 times) is a: A) Prime number B) Composite Number C) divisible by $\frac{10^7 -1}{9}$ The answer is B ...
-1
votes
1answer
66 views

Prove that for every positive integer $n>0$, $3\sum\limits_{i=1}^n i^5 $ is divisible by $\sum\limits_{i=1}^n i^3$ [closed]

Can you help me with this problem : Prove that for every positive integer $n>0$, $3\sum\limits_{i=1}^n i^5 $ is divisible by $\sum\limits_{i=1}^n i^3 $
1
vote
2answers
149 views

Describe the Natural density of $p$ which divides natural numbers of the form $n^2+1$?

We want to find the numbers that divide natural numbers in the form of $n^2+1$ and solve for their natural density. Using Wolfram Mathematica, I found divisors from $n=0$ to $1000000$ and eliminated ...
1
vote
2answers
54 views

Prove that if there are integers $m$ and $n$ such that $am +bn =1$ then $a$ and $b$ are coprime.

Suppose $a,b \in \mathbb{N}$. Prove that if there are integers $m$ and $n$ such that $am +bn =1$ then $a$ and $b$ are coprime. I came up with the following proof, but I am sure a shorter argument ...
1
vote
1answer
40 views

How to prove that if $(ab,n)=1$ then, $(r,n)=1$? [duplicate]

Let $ab=nq+r$ where all variables represent integers with $0\leq r<n$. If $(ab,n)=1$ then how to prove that $(r,n)=1$? I need to prove this to help me understand the proof of Euler's theorem better....
2
votes
3answers
136 views

Why does the statement “p is prime if it is divisible by only itself and 1” define only one prime number? [closed]

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 ...
0
votes
0answers
35 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 ...
4
votes
2answers
63 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 \...