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

learn more… | top users | synonyms

3
votes
3answers
146 views

LCM of $n$ consecutive natural numbers

Is there an efficient way to calculate the least common multiple of $n$ consecutive natural numbers? For example, suppose $a = 3$ and $b = 5$, and you need to find the LCM of $(3,4,5)$. Then the LCM ...
14
votes
5answers
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 ...
2
votes
1answer
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$...
1
vote
2answers
65 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 ...
1
vote
2answers
114 views

Prove that if $n|5^n + 8^n$, then $13|n$ using induction

I have to prove using mathematical induction that if $n \ge 2$ and $n|5^n + 8^n$, then $13|n$. Please help me.
0
votes
0answers
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: ...
0
votes
1answer
29 views

Prove: For any integers $p$ and $q$, if $p$ is odd and $q$ is even, then $8p + 5q − 7$ is odd.

Is this proof done correctly? $8(2k+1)+5(2k)-7 = 2k+1$ $16k+8+10k-7=2k+1$ $26k+1 = 2k+1$ One of our hints says: An integer $n$ is a multiple of $a$ iff $n = ak$ for some integer $k$. (When $a =...
0
votes
1answer
40 views

Prove that $2^d$ is not congruent to $1 \mod p^2$

We have $p>2$ - prime number and we know that $2^n\equiv 1\mod p$ and $2^n$ is not congruent to $1 \mod p^2$ ($n$-natural number). Prove that $2^d$ is not congruent to $1 \mod p^2$ where order $2 = ...
2
votes
1answer
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. ...
2
votes
4answers
85 views

Show that: $97|2^{48}-1$

Show that: $97|2^{48}-1$ My work: $$\begin{align} 2^{96}&\equiv{1}\pmod{97}\\ \implies (2^{48}-1)(2^{48}+1)&=97k\\ \implies (2^{24}-1)(2^{24}+1)(2^{48}+1) &=97k\\ \implies (2^{12}-1)(2^{...
2
votes
1answer
38 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.
1
vote
2answers
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 ...
2
votes
2answers
57 views

Show that :$89|2^{44}-1$

Show that :$89|2^{44}-1$ Using Fermat's theorem we have: $2^{88}\equiv{1}\pmod{89}\ \Rightarrow\ (2^{44}-1)(2^{44}+1)=89k$ , now how can be sure that: $89|2^{44}-1$??
1
vote
3answers
320 views

Prove for positive integers a,b,c and d (where b does not equal d), if gcd(a,b) = gcd(c,d) = 1, then a/b + c/d is not an integer

Prove for positive integers $a,b,c$ and $d$ (where $b$ does not equal $d$), if $\gcd(a,b) = \gcd(c,d) = 1$, then $a/b + c/d$ is not an integer. I understand that if $\gcd(a,b)$ and $\gcd(c,d) = 1$, ...
2
votes
3answers
57 views

$a^3+b^3+c^3\equiv{0}\pmod7\implies $ at least one of $a,b$ or $c$ is divisible by $7$

Show that if $a^3+b^3+c^3\equiv{0}\pmod7\implies$ at least one of $a,b$ or $c$ is divisible by $7$. Here it seems Fermat's theorem has no use. We could consider many different cases of remainders of ...
4
votes
2answers
63 views

Show that $1^7+7^7+13^7+19^7+23^7\equiv{0}\pmod{63}$

Show that $1^7+7^7+13^7+19^7+23^7\equiv{0}\pmod{63}$ According to Fermat's theorem: $$1^7+7^7+13^7+19^7+23^7\equiv{1+7+13+19+23}\pmod{7}\equiv{63}\pmod{7}\equiv{0}\pmod{7}$$ Now we need to show: $1^7+...
7
votes
1answer
53 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 ...
-2
votes
2answers
80 views

Prove or disprove $x^2-x$ is divisible by $x$ [closed]

Can someone prove or disprove this statement: Given a positive integer $x>1$, is it true that $x^2-x$ gives a number that is divisible by $x$?
0
votes
3answers
92 views

Prove that $\gcd(e,f)=1$.

Could someone please help me with this proof? Suppose that $a, b \in N$, and $d = \gcd(a, b)$. Since $d$ divides $a$, we have $a = de$ for some integer $e,$ and similarly $b = df$ for some integer ...
0
votes
2answers
38 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?
1
vote
2answers
35 views

Rayleigh quotient $Q=(\frac{||\triangledown w||}{||w||})^2$ in using the eigenfunction $\sin(x)$ on the segment $(0,\pi)$

I would like to well understanding the Rayleigh quotient $Q=(\frac{\|\nabla w\|}{\|w\|})^2$. Does anyone could explain to me why we divide the norm of the gradient $\| \nabla w \|$ by $\| w \|$, and ...
3
votes
1answer
148 views

Prove that $(a-b)^n\mid (a^n-b^n) \iff n=1$ under given conditions

Suppose that $a,b,(a-b)$ are pairwise co-prime (i.e. $a\perp b\perp (a-b)\perp a$), and that $\frac{a}{2}<b<a$, where $a$ and $b$ are both positive integers greater than $2$. Let $n$ be odd. ...
9
votes
5answers
143 views

Prove that $2^n$ does not divide $n!$

I want to prove that $2^n$ does not divide $n!$. I was trying by induction and I'm confused about if what I'm doing is right. First I test it with $n=1$. In fact: $$2^1 \nmid 1!$$ So if i take the ...
0
votes
1answer
56 views

Divisibility of a summation by $p^2$

I try to use the hint of this problem but I could not. Any detailed answer will be appreciated! Let $p$ be a prime number which $p>3$, and $$a/b:=1+1/2+1/3+\cdots +1/(p-1).$$ How could we show ...
2
votes
2answers
243 views

Connection between GCD and totient function

I found the following formula which connects Euler's totient function with gcd at wikipedia. $$ \gcd(a,b) = \sum_{k|a \; \hbox{and} \; k|b} \varphi(k). $$ The problem is that I can not figure out ...
1
vote
2answers
73 views

If $a \in A$ and $b \in B$ then $2a \in B$ and $2b \in A$ and $(a+b)^{2014}\in C$ [closed]

Below are questions that it think I know how to do but im not $100\%$ sure. $(i)$ asks if $a$ is odd so $a=k+1$, then prove $2a$ is even so $2a = 2k+2.$ The second and third differ a little am I ...
2
votes
4answers
105 views

Prove that $n^4-n^2$ is divisible by $8$ if $n$ is an odd positive integer.

Prove that $n^4-n^2$ is divisible by $8$ if $n$ is an odd positive integer. I'm supposed to use proof by induction, but I failed at it miserably. So far I have this: $$(n^4) - (n^2) = (n^2)((n^2)-1)...
12
votes
0answers
172 views

Have I discovered an analytic function allowing quick factorization?

So I have this apparently smooth, parametrized function: The function has a single parameter $ m $ and approaches infinity at every $x$ that divides $m$. It is then defined for real $x$ apart ...
0
votes
1answer
27 views

Find all $(a,b) \in \Bbb Z^2$ such that $b \equiv 2a \pmod 5$ and $28a+10b=26$

I'm stuck with this exercise: Find all $(a,b) \in \Bbb Z^2$ such that $b \equiv 2a \pmod 5$ and $28a+10b=26$ It's from my algebra class, we are looking into diophantic and congruence equations. ...
0
votes
2answers
51 views

Proof for any natural n that: $8|5^n+2*3^{n-1}+1$

I used this method for proving this statement but I came up with a problem. $ 5^n+2*3^{n-1}+1 \equiv 1 + 25^{n/2} + 2 * 81^{(n-1)/4} \equiv 4 \pmod{8}$ What is the problem with my solution?
7
votes
2answers
64 views

Find all odd $n \in \mathbb{Z}^+$ such that $n\mid 3^n+1$.

Find all odd $n \in \mathbb{Z}^+$ such that $n\mid 3^n+1$. I believe that there doesn't exist any such $n$ except $1$. It is clear that $n$ can't be a multiple of $3$. Also, $3^n \equiv -1 \pmod n$. ...
1
vote
3answers
95 views

Divisibility of $n^4 -n^2$ by 4 (induction proof)

We have to show that $$ n^4 -n^2 $$ is divisible by 3 and 4 by mathematical induction Proving the first case is easy however I do not know how what to do in the inductive step. Thank you.
1
vote
2answers
23 views

Find $b \in \Bbb Z$ for which exists $a \equiv 4 \pmod 5$ such that $6a+21b=15$

I'm starting to study diophantic equations and congruence and I have found this problem that I don't know how to solve: Find $b \in \Bbb Z$ for which exists $a \equiv 4 \pmod 5$ such that $6a+21b=...
4
votes
1answer
54 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 ...
2
votes
1answer
29 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 ...
0
votes
0answers
11 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
73 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
31 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
75 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 prove ...
0
votes
0answers
29 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 \mathbb{...
1
vote
4answers
178 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
63 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
26 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$ ...
0
votes
5answers
75 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
937 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
140 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
42 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 .