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.

10
votes
1answer
160 views

Proving or disproving $12\mid x$ given $x^2+2\mid y^2-2$

Let $x$, $y$ be positive integers such that $x^2+2\mid y^2-2$. Prove or disprove that $12\mid x$. This conclusion comes when I was dealing with another problem, and I feel it is right because when $x=...
1
vote
2answers
72 views

Find the smallest $n$ such that the $n$-th prime $p_n \equiv 330 \mod n $.

Find the smallest $n > 1$ such that the $n$-th prime $p_n \equiv 330 \mod n $. I was investigating the remainders when the $n$-th prime is divided by $n$. For every positive integer $a < 330$, ...
17
votes
7answers
51k views

Is division of matrices possible?

Is it possible to divide a matrix by another? If yes, What will be the result of $\dfrac AB$ if $$ A = \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}, ...
0
votes
1answer
21 views

A problem with an infinite multitude of numbers that follow some rules

We call the number n a "special number" if there are three distinct natural numbers divisors (of n) so that the sum of their squares is equal to n. We know that n is a natural number and n is diffrent ...
4
votes
4answers
204 views

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$...
2
votes
3answers
56 views

If $p$ is prime then $p^{n-1}\mid \binom{p^n}{p}$.

I am stuck with this problem: If $p$ is prime then $p^{n-1}\mid \binom{p^n}{p}$. The thing is that I don't know much properties of binomial coefficients and I'd accepts hints.
0
votes
1answer
26 views

Divisor Properties

This is a general question regarding divisibility If $c|a$ and $c|b$, does $c|a+b$? Where $a,b,c$ are integers If yes, does this also hold for general rings?
4
votes
3answers
34k views

What is the remainder when 4 to the power 1000 is divided by 7

What is the remainder when $4^{1000}$ is divided by 7? In my book the problem is solved, but I am unable to understand the approach. Please help me understand - Solution - To find the ...
0
votes
1answer
42 views

Perfect squares and divisor

Let $n$ be a positive integer and let $d$ be a positive divisor of $2n^2$. Prove that $n^2+d$ is not a perfect square. My working: $d \mid 2n^2$ Let $d \cdot k=2n^2 \implies d=\dfrac {2n^2}k$ ...
15
votes
3answers
831 views

Are associates unit multiples in a commutative ring with $1$?

My problem is: Are associates unit multiples in a commutative ring $R$ with $1$? Recall $a$ and $b$ are associates in $R$ if $\,a\mid b\mid a\,$ in $R$ or, equivalently $\,aR = bR,\,$ and $\,a,b\,...
6
votes
7answers
4k views

Prove that $6$ divides $n(n + 1)(n + 2)$

I am stuck on this problem, and was wondering if anyone could help me out with this. The question is as follows: Let $n$ be an integer such that $n ≥ 1$. Prove that $6$ divides $n(n + 1)(n + 2)$. ...
0
votes
4answers
45 views

I am looking for a proof of a certain set being divisible by 7

I am looking for a proof of this statement: $$7\mid{3^{6k+2}-{2^{6k+1}}}$$ By trial and error I can see that it holds but I cant figure out anyway to prove it or cant seem to be able understand why. ...
2
votes
1answer
70 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
10 views

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

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
4answers
251 views

How to show $a^{2^n}+1 \mid a^{2^m}-1$?

I've been struggling with this all day today. I imagine it's not very hard, but my algebra skills are terrible. So, how can I show that if $m>n$ and $a$ is a positive integer, then $$a^{2^n}+1 \mid ...
3
votes
0answers
88 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 ...
5
votes
1answer
66 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 ...
-1
votes
2answers
33 views

Divisibility Theory [closed]

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.
7
votes
2answers
112 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
vote
1answer
40 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 ...
0
votes
1answer
8 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
54 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 ?
2
votes
4answers
79 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 ...
13
votes
1answer
9k views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
0
votes
0answers
64 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
2answers
39 views

Slowest-growing divisibility sequence?

There are divisibility sequences of the form $\frac{p^k-1}{p-1}$ which have the property that if $a \mid b$, then $f(a) \mid f(b)$, ensuring (among other things) that only prime indices of the ...
3
votes
1answer
124 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
5answers
1k views

Prove that $2^{5n + 1} + 5^{n + 2} $ is divisible by 27 for any positive integer

My question is related to using mathematical induction to prove that $2^{5n + 1} + 5^{n + 2} $ is divisible by 27 for any positive integer. Work so far: (1) For n = 1: $2^{5(1) + 1} + 5^{(1) + ...
1
vote
1answer
26 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
3answers
42 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 ...
2
votes
2answers
81 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
4answers
182 views

Whis is $\gcd(x^4+1,x^2-1) = 1$ but I get $2$ by the Euclidean algorithm?

I need to find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidean algorithm. Wolfram shows that the gcd is equal to $1$, but for some reason I don't get the same answer. ...
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 ...
4
votes
1answer
176 views

A solution using 'Lifting the exponent' lemma to IMO 1990 P3

Question: Find all positive integers $n$ such that $$n^2\mid 2^n+1$$ My solution: Lemma (Lifting the exponent): Let $v_p(n)$ denote the highest power of a prime $p$ that divides $n$. That is, $v_p(...
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
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 ...
1
vote
1answer
62 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
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)
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$ ...
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 ...
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
3answers
95 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}-...
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 ...
-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. ...
0
votes
2answers
58 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
42 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 ...
6
votes
3answers
5k views

Proving gcd($a,b$)lcm($a,b$) = $|ab|$

Let $a$ and $b$ be two integers. Prove that $$ dm = \left|ab\right| ,$$ where $d = \gcd\left(a,b\right)$ and $m = \operatorname{lcm}\left(a,b\right)$. So I went about by saying that $a = p_1p_2......