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

learn more… | top users | synonyms

1
vote
1answer
24 views

How many $3$ digit different number that will be divisible by $5$ can be formed from the digit $0,2,3,4,5,6$ lying between $100$ and $1000$.

How many $3$ digit different number that will be divisible by $5$ can be formed from the digit $0,2,3,4,5,6$ lying between $100$ and $1000$. My attempt: Divisible by $5$ is possible only when ...
4
votes
1answer
46 views

Prove that if $p \mid a-b$ then $p^{n+1} \mid a^{p^n}-b^{p^n}$

I need help with the following problem, I don't know how to continue. Let $p$ be a prime. Prove that if $p \mid a-b$ then: $$p^{n+1} \mid a^{p^n}-b^{p^n}$$ At first I thougt the following: $$p \mid ...
0
votes
0answers
14 views

Lattices and Boolean algebra

I have read in a text book that the set of natural numbers form a lattice under divisibility. How can it possibe, since there is no upper bound and therefore a Sup of the set?
0
votes
0answers
9 views

Need help in understanding a solution regarding divisibility

I found this question in the mathematical circles textbook which asked if a number with a hundred 0's , hundred 1's and hundred 2's be a perfect square. As of a solution they pointed out that the ...
1
vote
2answers
70 views

How to find remainder of a very large number when divisor is 17?

How to find the remainder when $2^{2015}$ is divided by $17$? I tried dividing $2,4,8,16$ etc by $17$ and finding the remainder in each case to form some particular sequence but failed can someone ...
1
vote
1answer
29 views

Dividing by something Undefined

I was thinking about trigonometry ratios, in particularly $\cot(\theta)$, which can be defined as $\cot(\theta) = \frac {1}{\tan(\theta)} = \frac {cos(\theta)}{sin(\theta)}$. Though $\tan(90)$ is not ...
3
votes
3answers
68 views

If $9 \mid 2^b-2^a$, then $7\mid2^b-2^a$

Prove that if $9 \mid 2^b-2^a$, then $7\mid2^b-2^a$. I am not sure how to prove this statement, but it seems that from $9 \mid 2^b-2^a$ we have $b-a = 6n$. Then what should I do from here to ...
0
votes
0answers
23 views

Two variables diophantine equation and divisibility

Let $n\in\mathbb{N}$ such that $n\mid35m+26$ and $n\mid 7m+3$. Find $m\in\mathbb{Z}$ I dont know how to start, i tried by writting $n=k_{1} (35m+26)=k_{2} (7m+3)$ for some $k_{1} , k_{2} \in ...
1
vote
4answers
170 views

Proving that an equation doesn't have integer solutions

I need to prove that there are no integer solutions for a bunch of equations like the following: $$15x^2 - 7y^2 = 9$$ I was able to solve some simpler ones by picking a dividend and looking into it's ...
5
votes
0answers
60 views

Show there are only a finite number of integers with $\dfrac{\prod_{i=1}^n a_i-1}{\prod_{i=1}^n (a_i-1)} $ an integer

Show, for each $n$, there are only a finite number of integral $(a_i)_{i=1}^n$ such that $2\le a_i \le a_{i+1}$ and $\dfrac{\prod_{i=1}^n a_i-1}{\prod_{i=1}^n (a_i-1)} $ is an integer. My question is ...
1
vote
1answer
26 views

Divisibility - what is A+B?

Is there an easy to solve this problem? I can find the answer by using a complicated rule that I don't understand. Even if I try to remember this rule, I probably will forget about it a year later. ...
1
vote
1answer
23 views

Find the remainder for $\sum_{i=1}^{n} (-1)^i \cdot i!$ when dividing by 36 $\forall n \in \Bbb N$

I need to find the remainder $\forall n \in \Bbb N$ when dividing by 36 of: $$\sum_{i=1}^{n} (-1)^i \cdot i!$$ I should use congruence or the definitions of integer division as that's whave we've ...
0
votes
3answers
85 views

proving for all odd integers that $n^2 + 2n \equiv 0 \pmod{3}$

prove that for all odd integers, $3 |(n^2 + 2n)$ An even integer may be described as $2k$ and an odd one as $(2k+1)$, inserting it in to our equation gives us $(2k+1)^2 + 2(2k+1) $ $=4k^2 + 8k + 3$ ...
1
vote
5answers
71 views

Prove that if $n$ is not divisible by $3$, then $n^2 \equiv 1 \pmod 3$

I can see that it is true for all cases where $n$ is not divisible by $3$, such as $n = 1$, $n = 2$, $n = 4$, etc. However I can't figure out how to prove it.
16
votes
4answers
891 views

Divisibility for 7

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = ...
2
votes
2answers
136 views

$ 1^k+2^k+3^k+…+(p-1)^k $ always a multiple of $p$?

I would appreciate if somebody could help me with the following problem: Q: For any prime number $p(p\geq 3), k=1,2,3,...,p-2$, why is $$ 1^k+2^k+3^k+...+(p-1)^k $$ always a multiple of $p$ ?
2
votes
2answers
39 views

A number is divisible by 13 [duplicate]

I am studying divisibility and come across this rule. I think the rule is too complicated and hard to understand and remember. What is the best way to judge whether a number is divisible by 13 without ...
2
votes
2answers
36 views

Limit of indeteminate form $1^{(∞)}$

If we consider the function $f(x)=[(ax+1)/(bx+2)]^{x}$ where $a$,$b$ >$0$ and a I tried as follows]1 But at end i got stuck .
0
votes
2answers
20 views
-1
votes
1answer
10 views

Analogue Tape how long do I have to record?

If I have 1200ft (feet) of tape. How long will I be able to record for at 7.5ips (inches per second) Thank you
3
votes
4answers
112 views

Proof that $3 \mid \left( a^2+b^2 \right)$ iff $3 \mid \gcd \left( a,b\right)$

After a lot of messing around today I curiously observed that $a^2+b^2$ is only divisible by 3 when both $a$ and $b$ contain factors of 3. I am trying to prove it without using modular arithmetic ...
9
votes
8answers
518 views

Prove that if $3\mid a^2+b^2$ then $3\mid a$ and $3\mid b$.

For elements $a$ and $b$ in the ring $\Bbb{Z}$ prove that if $3\mid a^2+b^2$ then $3\mid a$ and $3\mid b$. I tried proving it but I just don't manage to. Maybe I am missing some basic claims in the ...
0
votes
2answers
443 views

How many 4-digit numbers with $3$, $4$, $6$ and $7$ are divisible by $44$?

Consider all four-digit numbers where each of the digits $3$, $4$, $6$ and $7$ occurs exactly once. How many of these numbers are divisible by $44$? My attack: There are $24$ possible four ...
-1
votes
2answers
25 views

If $a,b,c \in Z$, $\gcd(a-b,b-c) = \gcd(a-b,a-c)$ [closed]

I need to prove that for every three integers $(a,b,c)$, the $\gcd(a-b,b-c) = \gcd(a-b,a-c)$. Assuming that a $a \ne b$. Having: $d_1 = \gcd(a-b,b-c)$ $d_2 = \gcd(a-b,a-c)$ How do i prove $d_1 = ...
0
votes
1answer
35 views

determine odd number pattern?

How can I determine series of such numbers which when keep dividing by 2 always produce odd quotient? For example: 15 15/2 = 7 (odd) (take only integer(floor) part) 7/2 = 3 (again odd) 3/2 = 1 (again ...
0
votes
1answer
57 views

Prove that $n^2+11n+2$ is not divisible by $12769$ [duplicate]

My Attempt : Prime factorisation of $12769$ is $113^2$ $n^2+11n+2-113^2m=0$ The conjugate of this quadratic equation becomes: $\sqrt {113 (113m+1)} $ which can never be a rational as ...
1
vote
5answers
121 views

Show that $n^2+11n+2$ is not divisible by $113^2$ ( n is integer)

Show that $n^2+11n+2$ is not divisible by $113^2$ ( n is integer) It's obvious that if we show $113$ doesn't divide $n^2+11n+2$ we are done...
44
votes
2answers
793 views

Fractals using just modulo operation

Let us calculate the remainder after division of $27$ by $10$. $27 \equiv 7 \pmod{10}$ We have $7$. So let's calculate the remainder after divison of $27$ by $7$. $ 27 \equiv 6 \pmod{7}$ Ok, so ...
2
votes
1answer
27 views

Find number of Distinct remainders when $2009$ is divided by all natural numbers

Find number of Distinct remainders when $2009$ is divided by all natural numbers. obviously if we divide $2009$ by numbers greater than $2009$ remainder is $2009$ so we have to find remainders when ...
1
vote
1answer
38 views

Ratio vs division

I remember reading somewhere that in ancient times they were not treating a ratio like a division as we do. I was wondering is there a subtle distinction between the concept of the ratio and the idea ...
0
votes
1answer
62 views

When and why does this divide?

I've been working a lot with forms of this type, $\lfloor\frac{f}{g}\rfloor-\lfloor\frac{f-1}{g}\rfloor=1$ if $g|f$ and $0$ otherwise. This is valid for any expression $f$ and $g$ of natural numbers ...
0
votes
4answers
65 views

A positive integer (in decimal notation) is divisible by 11 $ \iff $ …

(I am aware there are similar questions on the forum) What is the Question? A positive integer (in decimal notation) is divisible by $11$ if and only if the difference of the sum of the digits in ...
4
votes
4answers
82 views

If $p > 3$ is prime, then $12 $ divides $p^2 - 1$

First up, I know there are a lot of similar questions with 24, not 12. So bare with me please :) What is the Question? Consider the following numbers of the form $p^2 - 1$ where $p$ is prime. $$5^2 ...
1
vote
3answers
32 views

Find the remainder of $\sum_{i=0}^{99} 2^{i^2}$ when dividing by 7 and determine if the quotient is even or odd

I've recently had this problem in an exam and couldn't solve it. Find the remainder of the following sum when dividing by 7 and determine if the quotient is even or odd: $$\sum_{i=0}^{99} 2^{i^2}$$ ...
1
vote
1answer
37 views

Problem to find all $n$ in following situation [closed]

Find all $n>1$ such that $1^{n} + 2^{n} + 3^{n} +\cdots + (n-1)^{n}$ divisible by $n$. I'm not good at Number Theory so , give elementary answer.
0
votes
1answer
18 views

Total number of integral solutions to the factors of a given numbet

Let $a$ be a factor of $120$ then what are the total number of positive integral solutions to $xyz=a$ including 120. The answer is $320$ . After wasting almost $15$ mins in getting the factors of each ...
6
votes
4answers
9k views

The product of n consecutive integers is divisible by n! (without using the properties of binomial coefficients)

How can we prove, without using the properties of binomial coefficients, the product of n consecutive integers is divisible by n factorial?
0
votes
0answers
36 views

Prove that $\frac{a^2+b^2}{1+ab}$ must be a perfect square [duplicate]

if $a$ and $b$ are positive integers and if $1+ab$ divides $a^2+b^2$ then prove that the quotient must be a perfect square. Let $$\frac{a^2+b^2}{1+ab}=k$$ where $k$ is some positive integer now ...
1
vote
0answers
320 views

Count arrays with GCD as D

Given N ,I need to count the number of array of integers which satisfy the following conditions : ...
2
votes
1answer
39 views

Dividing primes

Let $p_1,\dots , p_{n+1}$ be distinct primes, let $\alpha_1, \dots , \alpha_n$ be integers, and let $a,b$ be integers. Suppose we had the equation: $$b^2p_{n+1} = a^2p_1^{\alpha_1}\dots ...
2
votes
2answers
61 views

Factorial Divisibility

Let $a$ and $b$ be positive integers greater than one. With that in mind, $$(a \cdot b)!$$ is not necessarily divisible by: a) $$a!^b$$ b) $$b!^a$$ c) $$a! \cdot b!$$ d) $${2}^{ab}$$ By ...
49
votes
10answers
13k views

Has there ever been an application of dividing by zero?

Regarding the expression $a/0$, according to Wikipedia: In ordinary arithmetic, the expression has no meaning, as there is no number which, multiplied by $0$, gives $a$ (assuming $a\not= 0$), and ...
6
votes
1answer
78 views

Show that among any consecutive $16$ natural numbers one is coprime to all others

Show that among any consecutive $16$ natural numbers one is coprime to all others. Is it useful to use the division algorithm on $16$? $16k,16k+1,16k+2,...16k+15$
12
votes
6answers
6k views

How can I prove that $n^7 - n$ is divisible by $42$ for any integer $n$?

I can see that this works for any integer $n$, but I can't figure out why this works, or why the number $42$ has this property.
9
votes
2answers
124 views

Is a function of $\mathbb N$ known producing only prime numbers?

It is well known that a polynomial $$f(n)=a_0+a_1n+a_2n^2+\cdots+a_kn^k$$ is composite for some number $n$. What about the function $f(n)=a^n+b$ ? Do positive integers $a$ and $b$ exists such ...
1
vote
2answers
82 views

Any digit written $6k$ times forms a number divisible by $13$

Any digit written $6k$ times (like $111111$, $222222222222222222222222$, etc.) forms a number divisible by $13$. (source: a solution taken from careerbless) I tested with many numbers and it ...
2
votes
4answers
63 views

Proving divisibility for $256 \mid 7^{2n} + 208n - 1$

I can't come up with a way of proving this: $$256 \mid 7^{2n} + 208n - 1\\ \forall n \in \Bbb N$$ I've tried by induction but couldn't see when to apply the inductive hypothesis... $$P(n+1) = ...
1
vote
0answers
20 views

How Euclidian Algorithm for division works with algebric expressions?

I am attending an introductory Number Theory class for Computer Science focused on cryptography. I have done some exercises with integers number but I have two exercises in which appears algebric ...
2
votes
1answer
21 views

Finding quotient and remainder for a division

We are starting with division and congruence in my algebra course... this is one of the first exercises for the division algorithm. I've done the first that were given with fixed values but now I have ...
13
votes
3answers
1k views

How to solve this algorithmic math olympiad problem?

So, today we had a local contest in my state to find eligible people for the international math olympiad "IMO" ... I was stuck with this very interesting algorithmic problem: Let $n$ be a natural ...