# Tagged Questions

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

196 views

### Are there infinitely many pairs of primes where each divides one more than the square of the other?

I have the following question on number theory that is eating my head. Are there infinitely many primes $p,q$ such that $p | (q^2 + 1)$ and $q | (p^2 + 1)$? I can see $13,5$ and $2,5$ has the ...
15 views

### Prove that the product of $n$ consecutive integers is divisible by $n!$ [duplicate]

Problem : Prove that the product of $n$ consectutive integers is divisible by $n!$. $n!\mid a(a+1)(a+2)...(a+n-1)$
61 views

### Remainder of $2^{125}/13$

Remainder of $2^{125}/13$ According to Microsoft Excel, the answer is 6 I was expecting a shorter pattern with remainders such as 3,6,12,... How to go about doing this simply? I thought of ...
107 views

### For what powers $k$ is the polynomial $n^k-1$ divisible by $(n-1)^2$? [closed]

How do you prove this? $$\left(n-1\right)^2\mid\left(n^k-1\right)\Longleftrightarrow\left(n-1\right)\mid k$$
110 views

### Why is $10^k - 1$ divisible by $9$?

I know it is obvious that $10^k-1$ will always be divisible by $9$ for some integer $k$, but I am curious how to actually prove this. $$10^k - 1 \equiv 0 \bmod 9$$ $$10^k \equiv 1 \bmod 9$$ ... and ...
66 views

198 views

### Showing that $2^6$ divides $3^{2264}-3^{104}$

Show that $3^{2264}-3^{104}$ is divisible by $2^6$. My attempt: Let $n=2263$. Since $a^{\phi(n)}\equiv 1 \pmod n$ and $$\phi(n)=(31-1)(73-1)=2264 -104$$ we conclude that $3^{2264}-3^{104}$ is ...
18 views

### Discrete Math Proof: Divisibility equivalence

For all integers $a$, $b$, $d$, if $d$ divides $a$, and $d$ divides $b$, then $d$ divides $(3a+2b)$ and $d$ divides $(2a+b)$. Prove the statement. What Assumptions do I need to make at the beginning ...
121 views

46 views

### An unexplained condition on $a$ in a proof on the primes?

Lemma A positive integer $n$ is a prime if $(n,p) = 1$ for every prime integer $p \leq \sqrt{n}$ Proof in my text Let $(n,p) = 1$ for every prime $p \leq \sqrt{n} \:$. Suppose $n$ is not a ...
43 views

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?
1k views

### how $1/0.5$ is equal to $2$?

My question is how $1/0.5$ is equal to $2$. I am not asking the mathematical justification that $1/0.5=10/5=2$. I know all this. I just want to know how it is two... a lay man justification. ...
473 views

### Show that $\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n d^{n-1},a-b)$

How to show that $$\gcd\bigg( {a^n-b^n \over a-b} ,a-b\bigg )=\gcd(n d^{n-1},a-b )$$ $a,b\in \mathbb Z$ where $d=\gcd(a,b)$? Note $\$ Some of the answers below were merged from this ...
48 views

### Is it proper to say that zero divided by an integer $x$ has a remainder of $x$?

Is, for instance, $$\frac{0}{3} = 0$$ with a remainder of $3$? Thank you (:
40 views

### Can it proved that the GCD does not divide the integer coefficients in the linear form of the GCD?

Let $d = (a,b)$ then $d = ax +by$ for some $x,y \in \mathbb{Z}$ I want to prove that $d \nmid x,y$. Motivation I'm trying to solve the following problem: If $a$ is prime to $b$ and $y$, $b$ is ...
63 views

### If $a_n$ is increasingly divisible by $2$ and not a multiple of $10$ then the sum of its digits goes to infinity

Let $(a_n)_{n \geq 0}$ be a sequence of positive integers not divisible by 10 such that the number of factors 2 in $a_n$ tends to inﬁnity for $n \to \infty$. Prove that the sum of the digits of an in ...
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 ...
63 views

124 views

### If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$

As stated in the title, the problem to prove is Let $a,b,c \in \mathbb{Z}$. If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$. I think I've proved it, but I would like a second opinion. Here goes:...
Show that among every consecutive 5 integers one is coprime to the others I considered these 5 numbers as: $5k,5k+1,5k+2,5k+3,5k+4$ It's seen that for example $5k+1$ is coprime to $5k$ and $5k+2$,now ...