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
3answers
55 views

Are there any divisibility rules using 7? [duplicate]

Divisibility rules of 1,2,3,4,5,6,8,9 are first or second grade math. Are there any divisibility rules for numbers with factors including 7. I noticed that the digits of 7x starting with x=1 to x=5 ...
2
votes
2answers
70 views

Number Theory- Mathematical Proof

I am trying to prove a theorem in my textbook using another theorem. What I need to show that if a,b, and c are positive integers, show that the least positive integer linear combination of a and b ...
1
vote
1answer
94 views

how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime?

Given that $$U_n=\underbrace{1\cdots1}_{n\text{ times}}$$ and $n >2$, how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime? Because $U_m= ...
1
vote
1answer
14 views

Is there a way to figure out the number of possible combinations in a given total using specific units

I'm not professional mathematician but I do love a math problem - this one, however has me stumped. I'm a UX Designer trying to figure out some guidelines for using tables in a page layout. The thing ...
2
votes
3answers
44 views

Prove for integers a, b, and c, if gcd(a, b) = 1, a|c, and b|c then ab|c

Prove for integers $a$, $b$, and $c$, if $\gcd(a, b) = 1$, $a|c$, and $b|c$ then $ab|c$. Part b of this question is: "Is the converse true? Prove or disprove accordingly?" Hey, so I've been drawing ...
0
votes
2answers
54 views

If $a\mid b$ then $\gcd(a,c) \leq \gcd(b,c)$

I need to show that: If $a\mid b$ then $\gcd(a,c) \leq \gcd(b,c)$ where $a,b,c$ are positive integers. I've come up with this, but I'm not 100% sure that it's correct: Assume $a\mid b$, then $a ...
1
vote
0answers
50 views

Given a number $N$ and a prime $P$, how many numbers $\leq N$ are divisable by P but not by any smaller primes?

The following Math Exchange question deals with a similar problem: not divisible by 2,3 or 5 but divisible by 7 However, the answers given become infeasible quite quickly because the amount of ...
2
votes
1answer
47 views

Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime.

Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime. Here $v_p(k)$ denotes the largest $\alpha\in\mathbb Z_{\ge 0}$ s.t. $p^\alpha\mid k$. We have ...
0
votes
3answers
55 views

Find remainder of $\frac{17^{235}}{ 23}$

I need to find remainder of $\frac{17^{235}}{ 23}$. This is supposed to be solved using the following method: $\varphi(23) = 22$ ${17}^{235} = (({17}^{22})^{10})\cdot {17}^{15}$ ${17}^{22}\equiv 1 ...
5
votes
4answers
190 views

Finding the possible Least Common Multiples of of numbers with Highest Common Factor 8

The Highest Common Factor of two numbers is 8. Which one of the following can never be their Least Common Multiple? The choices are as follow: A. 8 B. 12 C. 60 D. 72 The answer key states ...
0
votes
1answer
38 views

Division with dividend less than divisor

Let $a\geq b$. We define the division of $a$ by $b$ to be, $$a=bq+r,$$ where $q,r$ are integers and $0\leq r<b$. How we divide $a$ by $b$ when $a<b$.?
5
votes
3answers
110 views

If $a^b=c^d$, then $c$ and $a$ are powers of the same number?

I want to know in which situations two numbers that can be expressed as powers can be equal. I think it's intuitive that if two powers (say $a^b$ and $c^d$) are equal, then the bases must be ...
0
votes
0answers
12 views

Given An initial point and final point ,How to determine the number of Co-Ordinates(x,y) such that both x and y are integral?

I have thought a lot about it and still no clue. I thought of visualising the initial point and the end point in the form of a Grid. But ,soon I was over with my resources. Problem: Given an initial ...
-1
votes
2answers
111 views

When will $ax+1$ be divisible by $b$?

Consider two natural numbers $a$ and $b$ such that $b$ is prime and $a$ is indivisible by $b$. Then, for which integral values of $x$ should $ax+1$ be divisible by $b$ ? I tried different values of ...
1
vote
1answer
26 views

Do we need to apply the Euclidean Algorithm before applying the Extended Euclidean Algorithm?

As the title says, do we need to apply the Euclidean Algorithm before applying the Extended Euclidean Algorithm? For example, we have $\gcd(24,17)$, so we can find $x,y$ such that $24x+17y=1$. ...
4
votes
1answer
40 views

Solving a Diophantine equation with LTE

Show that only positive integer value of $a$ for which $$4(a^n+1)$$ is a perfect cube for all positive integers $n$, is $1$. Rewriting the equation we obtain: $$4(a^n+1)=k^3$$ It is obvious that $k$ ...
3
votes
2answers
550 views

The sum of digits of $3(3x+3)$ is always $9$ for any $x$ between $1$ and $9$

Given the following 'joke' I stumbled across today It's easy enough to figure out that the answer is always 9. Asshole. However when I tried to 'prove' this for ...
0
votes
2answers
495 views

Question of remainder on dividing by 7

Question : What is the remainder when $$ 10^{10} + 10^{10^2} +10^{10^3} + \ldots + 10^{10^{100}} $$ is divided by $7$?
2
votes
5answers
309 views

Triple fractions

I've got this simple assignment, to find out the density for a give sphere with a radius = 2cm and the mass 296g. It seems straightforward, but it all got hairy when i've got to a fraction with three ...
57
votes
7answers
7k views

What makes $9$ special?

I don't know if this is a well know fact but I have observed that every number no matter how large that is equally divided by $9$, will equal $9$ if you add all the numbers it is made from until there ...
3
votes
2answers
74 views

Why is the sum of the digits in a multiple of 9 also a multiple of 9?

The sum of the digits in $9 k$ (where $k$ is an integer) is a multiple of $9$: for example $$9\cdot 1=9$$ $$9\cdot 7=63 \qquad \text{and } 6+3=9\cdot 1$$ $$9\cdot 11=99 \qquad \text{and } ...
5
votes
2answers
1k views

Prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$

So, if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$ means $1=ax+by$, and want to show $a^2x+b^2y=1$. By squaring $1=ax+by$ both sides, I get, $1=(ax)^2+b(2axby+by^2)$. It doesn't help my proof. Please help ...
2
votes
1answer
62 views

Show that $\prod _{i<j}(x_i-x_j)$ can be divided wihout remainder in $\prod_{i<j}(i-j)$ [duplicate]

Let $x_1,...,x_n$ be a natural numbers, show that $\prod _{i<j}(x_i-x_j)$ can be divided wihout remainder in $\prod_{i<j}(i-j)$ I know $\prod \left(x_i-x_j\right)$ is the result of ...
4
votes
5answers
84 views

$p$ divides $n^p-n$

Its very easy to prove $p\mid n^p-n$ for p=3,5,7, it fails for p=9 because $$ (n+1)^9-(n+1)= n^9+9n^8+36n^7+84n^6+126n^5+126n^4+84 n^3+36n^2+8n $$ and $84= 2²\times 3\times7$. Is it true for ...
2
votes
2answers
635 views

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$ I think I got it, but is this proof correct? We can write any integer x in the form: $x = 6k, x = 6k + 1, x = 6k + 2, x = 6k + 3, x = 6k + ...
5
votes
1answer
74 views

Non existence of absolute euler pseudoprimes

A natural number $n$ is called an Euler pseudoprime(sometimes Euler-Jacobi pseudoprime) wrt to $a$ iff $$a^{(\frac{n-1}2)} \equiv \Big(\frac an\Big) \pmod n$$ where $\Big(\frac an\Big)$ is the ...
1
vote
0answers
100 views

$p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?

Let $p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?
8
votes
4answers
359 views

Find the sum of reciprocals of divisors given the sum of divisors

Let $d_1, d_2, \cdots d_k$ be all the factors of a positive integer '$n$' including $1$ and $n$. Suppose $d_1 + d_2 + d_3+\cdots+d_k = 72$. Then find the value of $\frac{1}{d_1}+\frac{1}{d_2}+\cdots + ...
2
votes
1answer
42 views

A number root of two irreducible polynomials?

I woke up today doing me a question: is there a complex number that is root of two different irreducible polynomials of $\mathbb{Q} [x]$? I think not but I'm not sure and I am trying to prove. Some ...
4
votes
6answers
125 views

Prove $7|x^2+y^2$ iff $7|x$ and $7|y$

The question is basically in the title: Prove $7|x^2+y^2$ iff $7|x$ and $7|y$ I get how to do it from $7|x$ and $7|y$ to $7|x^2+y^2$, but not the other way around. Help is appreciated! Thanks.
2
votes
4answers
92 views

If the sum of two squares is divisible by $7$, both numbers are divisible by $7$ [closed]

How do I prove that if $7\mid a^2+b^2$, then $7\mid a$ and $7\mid b$? I am not allowed to use modular arithmetic. Assuming $7$ divides $a^2+b^2$, how do I prove that the sum of the squares of ...
1
vote
3answers
53 views

Divisibility of a polynomial by another polynomial

I have this question: Find all numbers $n\geq 1$ for which the polynomial $x^{n+1}+x^n+1$ is divisible by $x^2-x+1$. How do I even begin? So far I have that $x^{n+1}+x^n+1 = ...
2
votes
3answers
91 views

Determining if all integers of the polynomial form $n^2+21n+1$ are prime

Suppose I had a statement that said For all positive integers of n, ${n^2 + 21n + 1}$ is prime. Attempt: The first thing that I decided to do was to try and factor it. I immediately saw that it ...
1
vote
3answers
29 views

Greatest common Divisor of negative numbers

To find gcd of negative numbers we can convert it to positive number and then find out the gcd. Will it make any difference?
-6
votes
2answers
91 views

Is 0/0 equal to 100%? [duplicate]

I've asked a heap of people this question and I can't get a definite answer. Some say it's 0%, 100% or just undefined. I know that Anything divided by zero is undefined. Anything divided by itself ...
-1
votes
1answer
36 views

If $\gcd(a,4)=\gcd(b,4)=2$, find $\gcd(a+b,4)$.

If the greatest common divisor (GCD) of $a$ and $4$ is $2$, and that of $b$ and $4$ is $2$, what is the GCD of $a+b$ and $4$? I tried writing $4$ as $2^2$. So GCD of $a$ and $2^2$ is $2$ and GCD of ...
4
votes
1answer
48 views

Smallest $a$ such that both $a$ and $a+5$ and $a$ and $a+7$ have a common factor

Which is the smallest integer number $a$ so that the highest common factor of $a$ and $a+5$ is not $1$ and the highest common factor of $a$ and $a+7$ is not $1$ either? I think that it is $35$. Am I ...
4
votes
5answers
363 views

What is easiest way to know it the large number divisible by 57

What is the easiest way to know if large number is divisible by 57? For example, how could I deduce that 57 divides 300000177?
0
votes
0answers
28 views

Divisibiltiy of the order of elements in a group

Let $G$ be a finite group and ket $y \in G$. How many elements $x \in G$ are there such that the order of $y$ is divisible by the order of $x$
2
votes
2answers
48 views

If $a\mid b+c$ and $\gcd(b,c)=1$, prove $\gcd(a,b)=\gcd(a,c)=1$

I have the following: $b+c=av$ for some integer $v$, and $a=dm$ and $b=dn$ for $d=\gcd(a,b)$ and some integers $m,n$. Then, $c=av-b=dmv-dn=d(mv-n)$. So, $d|c$, and we know that $d|a$ and $d|b$. I ...
6
votes
8answers
342 views

If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
3
votes
1answer
43 views

Prove that for any positive integer $n$ the number $1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3+\cdots$ is divisible by $2^{n-1}$.

Let $a=4k-1$, where $k \in \mathbb{Z}$. Prove that for any positive integer $n$ the number $$1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3+\cdots$$ is divisible by $2^{n-1}$. My ...
2
votes
0answers
32 views

Finding solutions to a symmetric divisibility condition $x\mid p(y),\;y\mid p(x)$

In general, are there strategies for finding all integers $x$ and $y$ such that $x \mid p(y)$ and $y \mid p(x)$ for some polynomial $p$ with integer coefficients? For example, could we find all ...
3
votes
2answers
52 views

A question on greatest common divisor

I had this question in the Maths Olympiad today. I couldn't solve the part of the greatest common divisor. Please help me understand how to solve it. The question was this: Let $P(x)=x^3+ax^2+b$ and ...
3
votes
2answers
67 views

Does $p^n$ divide $\binom{p^{n+m-1}}{m}$?

Let $n, m \in \mathbf N$ and $p$ an odd prime number. Then does $p^n$ divide $\binom{p^{n+m-1}}{m}$ ? It seems true, but I can not find a clue. Can I have any hint?
4
votes
10answers
293 views

Why does the largest $x$ such that $a$, $b$ divided by $x$ leave the same remainder equal $a-b$?

Suppose two numbers $a$ and $b$ as, $a=kq_1+r_1=3\times 17 + 1 = 52$ and $b = kq_2+r_2=3 \times 15 +1=46$. It is clear that $52$ and $46$ leave the same reminder 1 when divided by $3$, because I ...
1
vote
5answers
129 views

Show that $30 \mid (n^9 - n)$

I am trying to show that $30 \mid (n^9 - n)$. I thought about using induction but I'm stuck at the induction step. Base Case: $n = 1 \implies 1^ 9 - 1 = 0$ and $30 \mid 0$. Induction Step: Assuming ...
0
votes
5answers
311 views

For every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$

I'm trying to prove that for every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$. The first part of this bi-conditional was easy for me to prove, but I'm having problems with the second. Here is ...
6
votes
3answers
1k views

Prove that every positive integer $n$ is a unique product of a square and a squarefree number

I am trying to prove that for every integer $n \ge 1$, there exists uniquely determined $a > 0$ and $b > 0$ such that $n = a^2 b$, where $b$ is squarefree. I am trying to prove this using the ...
1
vote
0answers
31 views

Number of binomial coefficients , ${ n \choose k}$ k $\in$ [0,n] , that are divisible by a prime p?

For a given k, ${n\choose k}$ is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding base p digit of k (consider the p-ary notation for n ...