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

learn more… | top users | synonyms

6
votes
1answer
67 views

Prove the sum of squares of 3 rationals cannot be 7

Prove there isn't $r_1, r_2,r_3 \in \mathbb{Q}$ so that ${r_1}^2 + {r_2}^2 + {r_3}^2=7 \tag1$ From (1) we get $a^2 + b^2 + c^2=7n^2 \tag2$ where $a,b,c,n \in \mathbb{N}$. I have tried playing ...
5
votes
6answers
104 views

Find a six digit integer [on hold]

Find an integer with six different digits such that the six digit integer is divisible by each of its digits. For example, find ABCDEF such that A, B, C, D, E and F all can divide the number ABCDEF. ...
6
votes
1answer
140 views
+50

Prove or disprove that $2^n$ divides $T_{2^n}$ for $n > 2$.

The Tribonacci sequence satisfies $$T_0 = T_1 = 0, T_2 = 1,$$ $$T_n = T_{n-1} + T_{n-2} + T_{n-3}.$$ Prove or disprove that $2^n$ divides $T_{2^n}$ for $n > 2$. (I think $2^n$ divides $T_{2^n}$...
4
votes
2answers
57 views

Let $P(x)=ax^{2014}-bx^{2015}+1$ and $Q(x)=x^2-2x+1$ such that $Q(x)|P(x)$, find $a+b$

Let $P(x)=ax^{2014}-bx^{2015}+1$ and $Q(x)=x^2-2x+1$ be the polynomials where $a$ and $b$ are real numbers. If polynomial $P$ is divisible by $Q$, what is the value of $a+b$. This is what I have ...
0
votes
1answer
11 views

Existence of a Repeating Divisor

I have $n$ integers $a_1, a_2, a_3, .., a_n$ let $X = a_1*a_2*a_3*...*a_n$. I want to know a single integer $F$ such that $F^2$ divides $X$. It is told that there will be atleast one such $X$ and ...
1
vote
3answers
75 views

What does it mean to say “a divides b”

I am not a number theorist and I am learning about relations. I encountered a relation that says $a \leq b$ if $a$ divides $b$ Can someone clarify what it means to a number to divide another ...
6
votes
4answers
78 views

Showing that for $f \in K[x]$, we have $f(x) \mid f(x + f(x))$

Let $K$ be a field an $f \in K[x]$. I now want to show that $f(x) \mid f(x + f(x))$ (in $K[x]$). I know that I need to find a polynomial $g \in K[x]$ so that $f(x) g(x) = f(x + f(x))$. So I thought ...
2
votes
2answers
296 views

Prime implies irreducible

In a unique factorization ring with unity (I am not considering commutativity and zero divisors in definition of UFD) irreducible implies prime. And it was proved in ring with unity without zero ...
1
vote
1answer
38 views

Unable to understand why gcd(bt+r,b)=gcd(b,r) [duplicate]

I am trying to understand greatest common divisor so If a=bt+r for integers t & r then why gcd(a,b)=gcd(b,r).I am unable to understand it.
0
votes
2answers
23 views

Find $a+b$ for $a, b$ such that $(x+1)^{n}(x^{2}+ax+b) \equiv 2^{n}(x-1) \mod (x-1)^{2}$

Since $2^{n} = \sum_{0}^{n}\binom{n}{k},$ we have from the given congruence the congruence $$\sum_{0}^{n}\binom{n}{k}(x^{k+2} + ax^{k+1} + bx^{k} - x +1) \equiv 0 \mod (x-1)^{2}.$$ The given answer ...
2
votes
5answers
62 views

Prove that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1$

Let $a$ and $b$ be two odd positive integers. Prove that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1$. I tried rewriting it to get $\gcd(2^{2k+1}+1,2^{\gcd(2k+1,2n+1)}-1)$, but I didn't see how this helps.
2
votes
1answer
33 views

For which odd positive integer $n$ , is it true that $-1$ is not a positive power of $2$ modulo $n$?

For which odd positive integer $n$ , is it true that $-1$ is not a positive power of $2$ modulo $n$ i.e. $[-1] \ne [2^k] , \forall k >0$ in $\mathbb Z_n$ ? Is there any ( at least sufficient ) ...
3
votes
4answers
93 views

$a^n$ even implies $a$ even

I've tried to prove that $(\forall a,n>0 \in \mathbb{N}),(a^n \text{ even} \implies a \text{ even})$, can someone tell me whether my proof is sound? Lemma 1: $a \text{ even} \implies a^2 \text{ ...
4
votes
1answer
74 views

Pattern in numbers

I bumped into this mathematical calculation while driving my car. With lot of traffic jams and lot of time to kill, I did some scrambling of the registration numbers of the cars in front of me. I ...
2
votes
1answer
24 views

Given a ring $R$ and a ring extension $R'$, if $r=r's$ where $r'\in R'\setminus R$, does that mean that $s\not\mid r$ in $R$?

Given a ring $R$ and a ring extension $R'$, if $r=r's$ where $r'\in R'\setminus R$ and $r,s\in R\setminus\{0\}$, does that mean that $s\not\mid r$ in $R$? I was thinking for example in $\Bbb{Z}$, ...
10
votes
2answers
334 views

Prove that $\gcd(3^n-2,2^n-3)=\gcd(5,2^n-3)$

Prove that $\gcd(3^n-2,2^n-3)=1$ if and only if $\gcd(5,2^n-3)=1$ where $n$ is a natural number. I didn't see an easy way to prove this using the Euclidean algorithm, but it seems true that both gcd'...
6
votes
8answers
430 views

If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
13
votes
9answers
421 views

Why does every number of shape ababab is divisible by $13$?

Why does it seems like every number $ababab$, where $a$ and $b$ are integers $[0, 9]$ is divisible by $13$? Ex: $747474$, $101010$, $777777$, $989898$, etc...
3
votes
4answers
46 views

Prove that if $a$ and $b$ are positive integers satisfying $\gcd(a,b)=\operatorname{lcm}(a,b)$,then $a=b$

Prove that if $a$ and $b$ are positive integers satisfying $\gcd(a,b)=\operatorname{lcm}(a,b)$,then $a=b$. Since the formula for two positive integers $a,b$ is $\operatorname{lcm}(a,b)=\frac{ab}{\...
1
vote
4answers
63 views

Prove using induction on n that: $8\mid5^n+2(3^{n-1})+1$

How can we use induction to prove that $8\mid5^n+2(3^{n-1})+1$ for any natural $n$?
1
vote
4answers
48 views

Show that if $\ 7|5a-2$ then $\ 49|a^2-5a-6\ $

Show that if $\ 7|5a-2$ then $\ 49|a^2-5a-6\ $ , ($\ a$ is positive integer) My work: $7|5a-2 \Rightarrow\ 49|35a-14a,49a^2 \Rightarrow\ 49|14a^2+14 \Rightarrow\ 42a^2+42a,49a^2+49a\ \Rightarrow\ ...
6
votes
2answers
212 views

Find the $k$ such that $2^{(k-1)n+1}$ does not divide $\frac{(kn)!}{n!}$.

Find all positive integers $k$ such that for any positive integer $n$, $2^{(k-1)n+1}$ does not divide $\frac{(kn)!}{n!}$. From olympiad problem I'm curious So far no one to solve this problem,Maybe ...
4
votes
1answer
115 views

IMO 1988 question No. 6 Possible values of $a$ and $b$, $\displaystyle\frac{a^2+b^2}{ab+1}$

I have a confusion in the question.The question is as follows: $a$ and $b$ are positive integers and $ab+1$ is a factor of $a^2+b^2$. Prove that $\displaystyle\frac{a^2+b^2}{ab+1}$ is a perfect ...
3
votes
2answers
102 views

Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$.

Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ for $0\ne a,b,c\in \Bbb{Z}$. I tried solving it with sets but I sense there are some details I am missing. I would truly appreciate your reference.
2
votes
8answers
200 views

Prove that $4$ divides $3^{2m+1} - 3$

Prove that $4$ divides $3^{2m+1} - 3$. By plugging in numbers I can see this is true, but I can't figure out a way to prove this, I was thinking maybe proving first that it is divisible by $2$, and ...
1
vote
4answers
131 views

Suppose that $a$ and $b$ satisfy $a^2b|a^3+b^3$. Prove that $a=b$.

Suppose that $a$ and $b \in \mathbb{Z}^+$ satisfy $a^2b|a^3+b^3$. Prove that $a=b$. I have reduced the above formulation to these two cases. Assuming $b = a + k$. Proving that any of the below two ...
1
vote
2answers
77 views

Numbers divisible by $11$ [duplicate]

A number is divisible by $11$, when the difference between the sum of the digits in the odd positions counting from the left (the first, third, ....) and the sum of the remaining digits is either 0 or ...
1
vote
0answers
32 views

Using Division Algorithm on Polynomials in Finite Field

From Ideals, Varieties, and Algorithms - Cox, Little, O'Shea. Chapter 1, Section 4. Ideals, Exercise 13 (b). Show that every $f \in \mathbb{F}_{2}[x,y]$ can be written as $f = A(x^2-x) + B(y^2-y)...
6
votes
4answers
264 views

How to prove that $4^{2n}-1$ is divisible by $3$ or $5$

My task is to prove that $4^{2n}-1$ is divisible by $3$ or $5$, with $n=1,2,3,...$. Any hints? What is the key observation? Thanks :)
1
vote
1answer
43 views

How to check if a number is prime? [closed]

I am having a problem with those numbers: 1) $2015^7 - 1$ 2) $817^2 + 53^2$. Especially when number is raised to a given power. My solution for the second point: $817^2$ is the same as checking $...
1
vote
2answers
41 views

Set of $4004$ positive integers so that the sum of any $2003$ of them is not divisible by $2003$

Is there a set of $4004$ positive integers so that the sum of any $2003$ of them be not divisible by $2003$? No idea how to start with, other than the fact that 2003 is a prime number.
1
vote
2answers
54 views

Remainder question with $6!$ and 7

Find the remainder when $6!$ is divided by 7. I know that you can answer this question by computing $6! = 720$ and then using short division, but is there a way to find the remainder without using ...
2
votes
1answer
55 views

The smallest number divisible by $c$ given conditions on the remainders

$a,b,c$ are positive integers such that: (1) $a<2b$ (2) the remainder on dividing $a$ by $b$ is $2r$; and (3) the remainder on dividing $a$ or $b$ by $c$ is $r$. Find the ...
2
votes
3answers
2k views

GCD Proof with Multiplication: gcd(ax,bx) = x$\cdot$gcd(a,b)

I was curious as to another method of proof for this: Given $a$, $b$, and $x$ are all natural numbers, $\gcd(ax,bx) = x \cdot \gcd(a,b)$ I'm confident I've found the method using a generic common ...
3
votes
2answers
43 views

Upper bound for $\gcd(a,b)$ if $\frac{a+1}{b}+\frac{b+1}{a}\in\Bbb{N}$

Suppose that $a,b$ are two positive integers so that $\frac{a+1}{b}+\frac{b+1}{a}$ is also a positive integer.Find the best upper bound for $\gcd(a,b)$. My work: $\frac{a+1}{b}+\frac{b+1}{a}=\frac{...
0
votes
1answer
72 views

Is there a quick way to tell what are the divisors of $11^{273}$?

An exercise its asking me to tell what are the divisors of $11^{273}$. My first thought was that any prime number raised to any number would be prime but this is not true ($2^2 = 4$ not prime). Since ...
2
votes
1answer
143 views

Show that $5^n$ divides $F_{5^n}$.

If $F_n$ denotes the $n$-th Fibonacci number ($F_0 = 0, F_1 = 1, F_{n+2} = F_{n+1} + F_n$), show that $5^n$ divides $F_{5^n}$.
2
votes
5answers
86 views

$E_{33}=\frac{10^{33}-1}{9}=$ divisible by $67$

Given $E_n =\frac{10^n-1}{9}=1+10+10^2....+10^{n-1}.$ Prove that $\;E_{33}$ is divisible by $67$ $E_{33}$ is such a large number thus one can not "simply" calculate whether $67$ divides $E_{33}$. ...
0
votes
6answers
71 views

Prove that $3$ divides $2^{2^n}$ − 1 for all integers $n ≥ 1$ [duplicate]

My answer: if $3|2^{2^n}-1$ then there must be an integer $j$ such that $3j=2^{2^n}-1$. then I needed help to continue if I am correct?
4
votes
3answers
207 views

Looking for an example of a GCD domain which is not a UFD

I know that every UFD (unique factorization domain) is a GCD domain i.e. g.c.d. of any two elements, not both zero, exists in the domain. I am looking for an example of a GCD domain which is not ...
0
votes
2answers
87 views

Prove that $\gcd(3^n-2,2^n-3)=1$ if and only if $\gcd(6^n-4,2^n-3)=1$ [duplicate]

Prove that $\gcd(3^n-2,2^n-3)=1$ if and only if $\gcd(6^n-4,2^n-3)=1$ where $n$ is a natural number. I was thinking of using something with the Euclidean algorithm, but I still don't see how to take ...
2
votes
1answer
130 views

The following is a necessary condition for a number to be prime, from its digit expansion. Has it been referred somewhere?

Concerning a numbers’ digits we know some necessary conditions on them for the number to be prime, besides the last digit having to be odd (except for prime 2). For example in decimal representation ...
1
vote
1answer
24 views

A question on divisibility of binomial coefficient

In this paper, page 3, theorem 4, the author claimed that If $m, n, k$ are three positive integer such that $\text{gcd}(n, k)=1$ then $\binom{mn}{k}\equiv 0\pmod n$. And he proved it as ...
1
vote
1answer
115 views

How to prove that $a \cdot b$ is not divisible by 5 for $\frac{1}{1} + \frac{1}{2} + … + \frac{1}{99} + \frac{1}{100} = \frac{a}{b}$? [duplicate]

Let $$\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{99} + \frac{1}{100} = \frac{a}{b},$$ where $a,b$ natural numbers and $\gcd(a,b) = 1$. How to prove that $a \times b$ is not divisible by $5$? ...
1
vote
1answer
17 views

multiple of an integer and asymptotics

Let us suppose that we have a positive integer $N$. We take the integer $\lceil \log_2 N \rceil$. Does there always exist an integer $X \geq N$ such that the following both conditions are satisfied: ...
0
votes
5answers
66 views

Divisiblity of an expression by 3

Doing a bit of work and came across a result I believe to be true but am not sure how to prove. Haven't done much work at all in number theory so any help r tips would be great. "$2^{k+1}-1$ is ...
0
votes
0answers
31 views

Closure of Poset $Q_n = \{x : x \mid n\}$

Let $(S, <)$ be a poset. A smallest poset $(S', <)$ is called a closure of poset $(S,<)$ iff $S$ is a subset of $S'$, $\operatorname{glb}(x,y)$ is in $S'$, and $\operatorname{lub}(x,y)$ is in ...
6
votes
0answers
74 views

Integer divisibility

Given a (not strictly) decreasing sequence of natural positive numbers $a_1, a_2, \dots, a_n$ prove that $$ \prod_{i<j} j-i \quad\big|\quad \prod_{i<j} a_i - a_j - i +j $$ I already know a ...