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
0answers
13 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
7 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
69 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
28 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
67 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
166 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
59 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
24 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. ...
3
votes
0answers
41 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 ...
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 ...
2
votes
2answers
38 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 .
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.
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
-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 ...
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 ...
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 ...
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
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 ...
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
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...
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 ...
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$
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 ...
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) = ...
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
1answer
33 views

Find all $n \in \Bbb Z$ such that $n^2 + n + 1$ divide $n^3-22$

I need help with this problem: Find all $n \in \Bbb Z$ such that $n^2 + n + 1$ divide $n^3-22$. I've got to a point where I know that $n^2 + n + 1 | -21$. So it should be among {${-21, -7, -3, -1, ...
2
votes
1answer
81 views

Prove that $(a+b+c)^{333}-a^{333}-b^{333}-c^{333}$ is divisible by $(a+b+c)^{3}-a^{3}-b^{3}-c^{3}$

Prove that $$(a+b+c)^{333}-a^{333}-b^{333}-c^{333}$$ is divisible by $$(a+b+c)^{3}-a^{3}-b^{3}-c^{3},$$ where $a,,b,c -$ integers, such that $(a+b+c)^{3}-a^{3}-b^{3}-c^{3}\not =0$ My ...
4
votes
2answers
280 views

Sum of squares of integers divisible by 3

Suppose that $n$ is a sum of squares of three integers divisible by $3$. Prove that it is also a sum of squares of three integers not divisible by $3$. From the condition, ...
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 ...
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 ...
0
votes
1answer
40 views

Number of solutions for $n^5 + 2 n^4 + n^3 - 3n + 2 $ mod $ 23^2 = 0$, where $0 \leq n < 23^2$ and $n\in \mathbb{N}$

$0 \leq n < 23^2$ and $n\in \mathbb{N}$ For how many $n$ $n^5 + 2 n^4 + n^3 - 3n + 2 $ mod $ 23^2 = 0$
0
votes
2answers
38 views

Demonstrate that $\int_0^1{\frac{(x^2+x+1)^{4n+1}- x}{x^2+1}dx}$ is a rational number

I thought about proving $x^2+1$ divides $(x^2+x+1)^{4n+1}- x$ , but I don't know how.
7
votes
0answers
76 views

Which prime factors of $8^{8^8}+1$ are known?

We have the partial factorization $$8^{8^8}+1=(2^{2^{24}}+1)\cdot (2^{2^{25}}-2^{2^{24}}+1)$$ The first factor is $F_{24}$. It is composite, but no prime factor is known. A prime factor of the ...
0
votes
0answers
12 views

Proof $\forall n \in \Bbb N$ that $2^n \cdot \prod_{i = 1}^{n} (2i-1)$ is divisible by $n!$

I'm trying to prove it by induction. $P(1)$ holds true. My inductive hypothesis is $n!\ |\ 2^n \frac {2n!} {2^n n!}$ which simplifies to $n!\ |\ \frac {2n!} {n!}$. Next $P(n+1)$: $$(n+1)!\ |\ 2^{n+1} ...
1
vote
0answers
13 views

Integer division and congruence exercise

I'm just starting with integer division and congruence in an algebra course and I have this problem: Let $a$ be an odd integer. Prove that $\forall n \in \Bbb N$: $$2^{n+2}\ |\ a^{2^n} - 1$$ I've ...
0
votes
0answers
19 views

Linear factor divides a function

I just came up with a simple question. If I have a polynomial function $f(x_1,x_2,\ldots,x_n)$ and I know that when $x_i=x_j, f=0$. Then does it imply $x_i-x_j$ divides $f$ for all $i\neq j$? If yes, ...
0
votes
1answer
23 views

Help with congruence and divisibility exercise

I'm starting to solve some problems of congruence and integer division, so the exercise is quite simple but I'm not sure I'm on the right track. I need to prove that the following is true for all $n ...
3
votes
2answers
56 views

if $p\mid a$ and $p\mid b$ then $p\mid \gcd(a,b)$

I would like to prove the following property : $$\forall (p,a,b)\in\mathbb{Z}^{3} \quad p\mid a \mbox{ and } p\mid b \implies p\mid \gcd(a,b)$$ Knowing that : Definition Given two ...
2
votes
1answer
39 views

Find all $n$ such that $n|1^n + 2^n + 3^n + \cdots + (n-1)^n$ where $n \in \mathbb{Z}^+$.

Find all $n$ such that $$n|1^n + 2^n + 3^n + \cdots + (n-1)^n$$ where $n \in \mathbb{Z}^+$. I don't know how to start. $n = 3, 5$ are simple solutions. Induction seems strange since the divisor ...