# Tagged Questions

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

2k views

### Can Mickey Mouse divide by $7$?

In the figure displayed in the image below : To find the remainder on dividing a number by $7$, start at node $0$, for each digit $D$ of the number, move along $D$ black arrows (for digit $0$ do ...
16 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 ...
124 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 ...
24 views

### Maximum length of a string that has no substring divisible by a prime number $p$ is $p-1$?

What is the maximum length of a string of nonzero digits that has no substring that is divisible by a given prime number? I want to find a string of length n which has no substring divisible by the ...
66 views

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

### If I know N%m , can I compute (N/2)%m? If yes, then how?

This question arrised when I was solving a computer science problem. I don't know the value of N, as N may be very large, but instead I know the value of $N \mod m$. Assume N is divisible by 2. How ...
36 views

### Divisible to the right in circle

Numbers $1,2,\dots,300$ are placed in a circle in some order. At most how many numbers can be divisible by the number to its right? One way (probably optimal) is to place numbers so that $m$ is ...
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 ...
63 views

### How can I prove $1^{n+2} + 2^{n+2} + 3^{n+2} + 4^{n+2}$ is divisible by $10$ for any odd $n$?

Assuming this is true: $1^n+2^n+3^n+4^n$ divisible by $10$ for any odd $n$ ($n$ is natural) How can I prove that for $n+2$: $1^{n+2} + 2^{n+2} + 3^{n+2} + 4^{n+2}$ Is divisible by 10 as well ? ...
63 views

47 views

### Conjecture about divisibility: if $d \mid n$, then there exists $r,s$ such that $n=r+s$ and $d = \gcd(r,s)$

Given $n\in\mathbb Z^+$. If $d<n>1$ and $d\mid n$ it exists $r,s\in \mathbb Z^+$ such that $n=r+s$ and $d=\gcd(r,s)$.
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 ...
200 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 ...
15 views

### If $N \neq p^k$, $(\sigma(N) - N) \mid (N - 1)$, and $3 \mid (N - 1)$, does it follow that $\nu_{3}(\sigma(N) - N) \neq \nu_{3}(N - 1)$?

(Note: This has been cross-posted from MO.) The title says it all. Let $\sigma=\sigma_{1}$ be the classical sum-of-divisors function. Here is my question: Original Problem (Note: This has been ...
36 views

### Is this enough to prove that the GCD is larger?

Prove that $(a+b, a-b) \geq (a, b)$ My attempt Let $(a+b, a-b) = d$ and $(a, b) = c$. Since $c \mid a,b$ $c$ is also a factor of $a+b$ and $a-b$. Thus $c \leq d$. Is this enough as a proof? It ...
43 views

### Can an odd perfect number be divisible by either $2049$ or $2051$?

Can an odd perfect number be divisible by either $2049$ or $2051$? Note that $2049 = 3 \cdot {683}$, and that $2051 = 7 \cdot {293}$. Added July 15 2016 It is known that an odd perfect number ...
36 views

101 views

48 views

### Does $n\mid(a^n-b^n)$ imply $n\mid(a^n-b^n)/(a-b)$? [duplicate]

Finding my previous question quite naive, I improve my question: Given that $n,a,b \in \mathbb{N}$ and $n\mid(a^n-b^n)$ , can we prove or disprove $n\mid(a^n-b^n)/(a-b)$ ?
65 views

### Does $n\mid(a^n-b^n)$ imply $n\mid(a-b)$?

Given that $n,a,b \in \mathbb{N}$ and $n\mid(a^n-b^n)$ , can we prove or disprove $n\mid(a-b)$ ? Using Fermat's little theorem, we can prove the case when n is a prime number. What about the case ...
68 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 ...
13 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 ...
119 views

### Find a six digit integer [closed]

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. ...
### 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 ...