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

learn more… | top users | synonyms

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 ...
5
votes
6answers
100 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. ...
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.
4
votes
2answers
54 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 ...
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.
5
votes
4answers
73 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
1answer
32 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 ) ...
1
vote
3answers
70 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 ...
2
votes
1answer
23 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}$, ...
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
73 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 ...
6
votes
1answer
108 views

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}$...
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)...
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
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
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 $...
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 ...
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 ...
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{...
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}$. ...
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 ...
2
votes
1answer
138 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}$.
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?
0
votes
2answers
71 views
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 ...
10
votes
2answers
327 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'...
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
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: ...
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 ...
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 ...
4
votes
1answer
113 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 ...
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 ...
0
votes
1answer
43 views

Help with finding the remainder of $2^{2^n}$ when divided by 13

I have this problem from an algebra course: Find the remainder of $2^{2^n}$ when divided by 13, $\forall n \in \Bbb N$ It's in a section of Fermat's little theorem and Chinese Remainder Theorem ...
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 ...
2
votes
1answer
15 views

Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$. Find the remainder of $a$ when divided by 70.

I'm stuck with this problem from my algebra class. We've recently been introduced to Fermat's little theorem and the Chinese Remainder Theorem. Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$...
13
votes
9answers
414 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...
14
votes
5answers
2k views

How can I tell if a number in base 5 is divisible by 3?

I know of the sum of digits divisible by 3 method, but it seems to not be working for base 5. How can I check if number in base 5 is divisible by 3 without ...
1
vote
2answers
66 views

prove if n - natural number divide number $34x^2-42xy+13y^2$ then n is sum of two square number

prove if n - natural number divide number $34x^2-42xy+13y^2$ where x,y are relatively prime then n is sum of two square number. I don't know what is going on in this exercise. I will be grateful ...
0
votes
0answers
24 views

why is area of a canvas being devided ?

Hey guy i am not so great at math and basically i have the following calculation that i need to figure out the entire formula ,looks like below: ...
2
votes
1answer
34 views

Prove that $3^{(q-1)/2} \equiv -1 \pmod q$ then q is prime number.

$q=2^m+1, m\ge 2$. Prove that if $$3^{(q-1)/2} \equiv -1 \pmod q$$ then q is prime number. I want to use if $q-1 | \phi(q)$, then q is prime number. But I don't know how to transform above equation. ...
0
votes
1answer
40 views

Prove that $2^d$ is not congruent to $1 \mod p^2$

We have $p>2$ - prime number and we know that $2^n\equiv 1\mod p$ and $2^n$ is not congruent to $1 \mod p^2$ ($n$-natural number). Prove that $2^d$ is not congruent to $1 \mod p^2$ where order $2 = ...
0
votes
1answer
29 views

Prove: For any integers $p$ and $q$, if $p$ is odd and $q$ is even, then $8p + 5q − 7$ is odd.

Is this proof done correctly? $8(2k+1)+5(2k)-7 = 2k+1$ $16k+8+10k-7=2k+1$ $26k+1 = 2k+1$ One of our hints says: An integer $n$ is a multiple of $a$ iff $n = ak$ for some integer $k$. (When $a =...
1
vote
2answers
49 views

$9 \mid a^2 +b^2+ab$. Show that $3$ divides both $a$ and $b$. [duplicate]

$a$ and $b$ are integers. $a^2 +b^2+ab$ is a multiple of $9$. I have to prove that $3$ divides both $a$ and $b$. Converse is very easy. Put $a=3k$ and $b=3l$ and that's it. I was trying ...
2
votes
1answer
38 views

find all primes $p$ and $q$ such that $p \cdot q | 2^p + 2^q$

I have to find all prime numbers $p,q$ such that $p\cdot q | 2^p + 2^q$. I don't know from what I have to start.
2
votes
4answers
85 views

Show that: $97|2^{48}-1$

Show that: $97|2^{48}-1$ My work: $$\begin{align} 2^{96}&\equiv{1}\pmod{97}\\ \implies (2^{48}-1)(2^{48}+1)&=97k\\ \implies (2^{24}-1)(2^{24}+1)(2^{48}+1) &=97k\\ \implies (2^{12}-1)(2^{...
2
votes
2answers
57 views

Show that :$89|2^{44}-1$

Show that :$89|2^{44}-1$ Using Fermat's theorem we have: $2^{88}\equiv{1}\pmod{89}\ \Rightarrow\ (2^{44}-1)(2^{44}+1)=89k$ , now how can be sure that: $89|2^{44}-1$??
2
votes
3answers
57 views

$a^3+b^3+c^3\equiv{0}\pmod7\implies $ at least one of $a,b$ or $c$ is divisible by $7$

Show that if $a^3+b^3+c^3\equiv{0}\pmod7\implies$ at least one of $a,b$ or $c$ is divisible by $7$. Here it seems Fermat's theorem has no use. We could consider many different cases of remainders of ...
4
votes
2answers
63 views

Show that $1^7+7^7+13^7+19^7+23^7\equiv{0}\pmod{63}$

Show that $1^7+7^7+13^7+19^7+23^7\equiv{0}\pmod{63}$ According to Fermat's theorem: $$1^7+7^7+13^7+19^7+23^7\equiv{1+7+13+19+23}\pmod{7}\equiv{63}\pmod{7}\equiv{0}\pmod{7}$$ Now we need to show: $1^7+...