# Tagged Questions

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

83 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 ...
36 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 ) ...
92 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 ...
45 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}$, ...
93 views

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 ...
44 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.
44 views

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}$. ...
132 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 ...
152 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}$.
78 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?
72 views

### Show that if $3n + 5$ is even, then $n^2$ is odd. [closed]

What approach should I take to prove this?
88 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 ...
363 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'...
28 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 ...
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: ...
213 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 ...
235 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 ...
138 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 ...
32 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 ...
80 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 ...
45 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 ...
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 ...
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$...
439 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...
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 ...
67 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 ...
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: ...
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. ...
40 views

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 ...
40 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.
89 views

58 views

### Function that turns GCD and LCM into intersections and unions?: $f(a)\cap f(b)=f(\gcd(a,b))$, $f(a)\cup f(b)=f(\operatorname{lcm}(a,b))$

Is there a function $f:\Bbb N_+\to\cal P(\Bbb N_+)$ such that: $f(a)\cap f(b)=f(\gcd(a,b))$, $f(a)\cup f(b)=f(\operatorname{lcm}(a,b))$, $a\in f(a)$, and $f$ is injective? Without the third ...
### 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$?