1
vote
1answer
20 views

Is my proof correct? Let $a, b, c\in\mathbb Z$. Prove that if $a\mid b$ and $b\mid c$, then $a\mid(b + c)$.

Let $a$, $b$, $c$ $\in\mathbb{Z}$. Prove that if $a\mid b$ and $b\mid c$, then $a\mid (b + c)$. My proof: since $a\mid b$, $b = k\cdot a$ for some integer $k$ since $b\mid c, c = l\cdot b$ for some ...
0
votes
0answers
36 views

Consecutive natural numbers [duplicate]

Please I want to know what is the most appropriate expression that if it is asked to find the counterexample of "The product of any three consecutive natural numbers is divisible by 9" My expression ...
0
votes
3answers
48 views

Prove that ac=bd implies a=d and b=c (if a,b relatively prime and c,d relatively prime)

Suppose that $\mathbf{a}$ and $\mathbf{b}$ are relatively prime, and that $\mathbf{c}$ and $\mathbf{d}$ are relatively prime. Prove that $\mathbf{ac = bd}$ implies $\mathbf{a = d}$ and $\mathbf{b = ...
4
votes
4answers
32 views

greatest common divisor of two primes a,b

Here is the question I am trying to prove: If $a,b$ are relatively prime and a>b prove that $\gcd(a-b, a+b) \in \{1, 2\}$. Can I begin with something like $(a-b)k + (a+b)l = d$ where $k,l$ are ...
2
votes
1answer
40 views

Finding divisibility of a

Let $$a=\frac{72!}{(36!)^2}-1$$ Find whether $a$ is odd. $a$ is even. $a$ is divisible by 71. $a$ is divisible by 73. Multiple answers can be correct. I was able to find whether $a$ is even or ...
0
votes
2answers
52 views

Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation?

Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation? I know that it's reflexive, since $\gcd(a,a) > 1$. It's also symmetric since $\gcd(a,b) > 1$ iff $\gcd(b,a) > 1$. ...
4
votes
2answers
36 views

Find all the polynomials $p \in \mathbb R [X]$ such that $(x+1)p=(p')^2$

(Where $p'(x)$ is the derivative of $p(x)$) Research effort: what I thought is that given that $(x+1)|(p')^2$ then $(x+1)|(p')$ (I'd like to justify better this, but I don't know how) Then, ...
2
votes
2answers
34 views

Let $a, b \in \Bbb Z$. Consider the following function: $f : ℤ \times ℤ \to ℤ$ such that for any$ (x,y)\in ℤ \times ℤ, f(x,y) = ax + by.$

Let $a, b \in ℤ$. Consider the following function: $f : ℤ \times ℤ \to ℤ$ such that for any $(x,y)∈ ℤ \times ℤ, f(x,y) = ax + by.$ Fill in the blank in the following proposition with a simple ...
1
vote
2answers
80 views

combinatorics and divisibilty

in how many ways we can form a $8$ digit numbers from $1,2,3,4,5$ with repetition allowed & divisible by $8$. MY APPROACH : to be divisible by 8 : last 3 digit of the no. must be divisible by 8 ...
0
votes
1answer
58 views

Congruence of $n^n$ modulo 5

Given a integer $n$, determine the remainder of dividing $n^n$ for 5 in terms of an adequate congruence for n. So I'm really stuck in this exercise. By Euler little theorem I know $n^4 \equiv 1 ...
3
votes
3answers
37 views

Divisibility in base $7$ problem

Find all integers between $0 \leq a \leq 2400$ such they are divisible by $8$ and that their base 7 development has at least $3$ equal digits.
0
votes
2answers
48 views

How can I prove this relation between gcd(a,b)?

I am stuck on starting this proof that involves gcd. Define $g_n=2^{2^n}+1$ and that $g_0g_1g_2...g_{n-1}=g_n-2$. Suppose that $a$ and $b$ are unequal positive integers. Prove that $gcd(g_a,g_b)=1$. ...
1
vote
1answer
33 views

Find all the $a$ such $539|a3^{253}+5^{44}$

This is what i thought: Given that $539|a3^{253}+5^{44}$ then $11|a3^{253}+5^{44}$ and $7^2|a3^{253}+5^{44}$ using congruences I get: $$a3^{253}+5^{44} \equiv 0 \pmod{7^2}$$ and ...
3
votes
2answers
68 views

Prove by induction $a-b|a^{n}-b^{n}$ for $n\in\mathbb N$

$P(1)$: $a-b|a-b$ $P(n) \Rightarrow P(n+1)$: $a-b|a^{n}-b^{n}\Rightarrow a-b|a^{n+1}-b^{n+1}$ I'm not sure how to proceed from here. Any help is appreciated.
1
vote
3answers
43 views

Prove by induction that $99 | 10^{2n} + 197$ for $n\ge 1$

I'm not sure whether I should make use of the transitive property, or this $a|b\Rightarrow b = a*z$ / $z\in\mathbb Z$ to solve the problem. I'm mainly looking to solve it through induction using the ...
1
vote
2answers
97 views

How many $7$ digits number can be made?

How many $7$ digits number can be made with $1,2,3,4,5,6,7$ so that they are divisible by $11$? (Repetition is not allowed.) I know the divisibility rule of $11$, so the main problem is counting.
0
votes
4answers
77 views

Prove that $2^{2k-1}+2^{k}+1$ is not divisible by $7$ for any $k$ natural number

I am trying to prove this, but I really can't seem to get anywhere with it.. I tried transforming this into something else, but no transformation yields in any useful expression whatsoever.. As ...
4
votes
6answers
194 views

Proof that $a^5 b - b^5 a$ is divisible by $30$ for any integers $a$ and $b$

I am trying to prove that $a^5\times b - b^5\times a$ is divisible by $3$. The actual task is to prove divisibility by $30$ but I have managed to prove that the expression is divisible by $5$ and $2$. ...
0
votes
2answers
48 views

What are a and b?

$a$ and $b$ are two positive integers. If $ab=1260$, $gcd(a,b)=3$, and when $a$ is divided by $b$ the remainder is 18, what are $a$ and $b$? How do you solve this? EDIT It looks like an ...
0
votes
0answers
75 views

Dynamic programming algorithm for GCD?

I can't seem to find a clear answer on this. I'm inclined to believe that there is not a DP solution for GCD, given the lack of information so far in my searches on the subject. I suppose that in ...
1
vote
1answer
47 views

Pigeonhole question - divisibility by chosen number

This question should be solved with pigeonhole principle. Let $a,n \in \mathbb N$ such that $a$ is a number whose digits are only $3$'s and $0$'s, and $n$ is an unspecified natural number. Show that ...
1
vote
1answer
30 views

Computations question

a) Determine the prime factorizations of 3850 and 4125 b) Find the value of d = gcd(3850,4125) c) List all the positive divisors of d This is what I have so far. a) 3850: 11, 5, 5, 7, 2 4125: ...
1
vote
1answer
23 views

finding unknowns and proof

The procedures for using cutting-adding method for testing a number M to be a multiple of 59 are as follows: 1 cut the units digit of M 2 add the remaining integer by r times of the deleted digit. 3 ...
1
vote
4answers
66 views

Prove that if $3|(a^2+b^2)$, then $3|a$ and $3|b$, where $a, b$ are integers [duplicate]

I would like to know how to prove the above statement by contradition. Somebody said that one should prove it by this method but I have no idea what it is.
0
votes
1answer
52 views

What is the concept behind divisibility of large numbers that contain only the digit 1?

An example question I found in a text book is : The 300 digit number with all digits equal to 1 is : A) Divisible by neither 37 nor 101 B) divisible by 37 but not by 101 C) divisible by 101 but not ...
5
votes
2answers
88 views

gcd Calculations

Let $a, b, c$ be integers. Prove that if $\gcd(a,b)=1$ then $\gcd(ab,c) = \gcd(a,c) \gcd(b,c)$ First time asking here. I'm not sure what your policies are on general homework help but I truly am ...
1
vote
3answers
73 views

Prove that any number of the form $a_3a_2a_1a_3a_2a_1$ is divisible by 91.

Prove that any number of the form $a_3a_2a_1a_3a_2a_1$ is divisible by 91. I got up to $a_3a_2a_1a_3a_2a_1$ = 1000001$a_3$ + 10010$a_2$ + 1100$a_1$. However none of the coefficients are divisible ...
3
votes
2answers
103 views

Prove Divisibility test for 11 [duplicate]

Prove Divisibility test for 11 "If you repeatedly subtract the ones digit and get 0, the number is divisible by 11" Example: 11825 -> 1182 - 5 = 1177 1177 -> 117 - 7 = 110 110 -> 11 - 0 = 11 11 ...
9
votes
1answer
548 views

Does $n \mid 2^{2^n+1}+1$ imply $n \mid 2^{2^{2^n+1}+1}+1$?

There are two ways to try to prove this. One is in the title, the other is its de Morgan counterpart: $n \nmid 2^{2^{2^n+1}+1}+1 \implies n \nmid 2^{2^n+1}+1$. Disproving it requires only one example ...
0
votes
2answers
162 views

calculate GCD of very large integers

How i can calculate GCD of two very large integers for example: gcd(31415926534676736647, 438478473847834834784748) either by hand or computer? is there any ...
2
votes
1answer
208 views
0
votes
1answer
52 views

Divisibility question with 8th powers

so I was assigned a divisibility question for homework. Prove that $27195^8-10887^8+10152^8$ is divisible by $26460$. Am I supposed to use mods? I appreciate the help!
0
votes
1answer
28 views

Showing the gcd of Integers can be Distributed

The Question: Use the theorem on classification of subgroups of $\mathbb{Z}$ to prove that, if $a_1,...,a_n \in \mathbb{Z}, gcd(a_1,...,a_n) = gcd(gcd(a_1,...,a_k),gcd(a_{k+1},...,a_n))$ for any $1 ...
5
votes
3answers
330 views

Prove that $2^n3^{2n}-1$ is always divisible by 17

Prove that $2^n3^{2n} -1$ is always divisible by $17$. I am very new to proofs and i was considering using proof by induction but I am not sure how to. I know you have to start by verifying the ...
0
votes
3answers
351 views

if $X^2 +AX+B=0$ has a rational root, prove it is an integer. [duplicate]

If $x^2 + Ax +B =0$ has a rational root, prove it is an integer. I don't even know where to start on this problem. I've had it on my white board for about a week and keep looking at it, but can't see ...
9
votes
4answers
370 views

Middle school number theory

Find at least three numbers that satisfy all three conditions: (1) there is a remainder of $1$ when the number is divided by $2$; (2) there is a remainder of $2$ when the number is divided by $3$; ...
1
vote
2answers
57 views

Proving divisibility of numbers

Let us take a two digit number and add it to its reverse.We have to prove that it is divisible by 11. Same way,if we subtract the larger number from the other,it is divisible by 9.How can we explain ...
1
vote
4answers
80 views

Find the greatest common divisor of the polynomials:

a) $X^m-1$ and $X^n-1$ $\in$ $Q[X]$ b) $X^m+a^m$ and $X^n+a^n$ $\in$ $Q[X]$ where $a$ $\in$ $Q$, $m,n$ $\in$ $N^*$ I will appreciate any explanations! THanks
5
votes
4answers
265 views

Prove or disprove the following statements involving greatest common divisor

Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
3
votes
1answer
98 views

Proof involving division algorithm

I'm trying to prove the following. Let $m$ and $n$ be positive integers, $n>m$. Prove that if $n$ divided by $m$ leaves remainder $r$, then $2^n - 1$ divided by $2^m-1$ leaves remainder ...
5
votes
2answers
148 views

How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?

How to prove $\forall m,n\in\mathbb N$: $$ 56786730 \mid mn(m^{60}-n^{60})?$$ Thanks in advance.
2
votes
5answers
132 views

Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$

Could you help me with the problem below? Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$. Thank you!
5
votes
1answer
86 views

$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1$, or $p$

Let $p$ be prime number ($p\gt2$) and $a,b\in\mathbb Z$ ,$a+b\neq0$ ,$\gcd(a,b)=1$ how to prove that $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1~~\text{or}~~ p$$ Thanks in advance .
3
votes
3answers
153 views

Divisibility problem: show $(x-z)\mid xy+zw \implies (x-z)\mid xw+yz$

I'm stuck at this homework problem can someone help me out? Much appreciated! $$(x-z)\mid xy+zw \implies (x-z)\mid xw+yz$$ Thanks again!
4
votes
3answers
49 views

Problems with proof that $p|2^m-2^n$ if $p-1|m-n$

This was a homework assignment that I have already made unsuccesfully. However, no answers were given and I'm still curious. The question is as follows: "If $p$ is an odd prime number and $m > n$ ...
4
votes
1answer
107 views

Is it allowed to divide an equation by an expression which can be equal to zero?

I need a help in such a problem and will greatly appreciate any suggestions. I was taught, division of an equation by an expression which can be equal to zero can lead to missing roots. But I thought ...
2
votes
2answers
231 views

Finding the smallest positive integer $N$ such that there are $25$ integers $x$ with $2 \leq \frac{N}{x} \leq 5$

Find the smallest positive integer $N$ such that there are exactly $25$ integers $x$ satisfying $2 \leq \frac{N}{x} \leq 5$.
1
vote
1answer
59 views

Solve for $px + q \equiv 0\pmod r$

How would I solve for the following in general: $(px + q)\equiv 0 \pmod r$ For example, $ (2x + 1)=0 \pmod 7 $ $x = 3, 10, 17, 24, \ldots $ $(9y + 5)= 0 \pmod 3 $ $y$ has no ...
13
votes
2answers
253 views

Prove $6 \nmid [\left( \sqrt[3]{28} - 3 \right)^{-n}]$

Prove that: $$6 \not\left|\ \left\lfloor\frac 1 {(\sqrt[3]{28} - 3)^{n}}\right\rfloor \ (n \in Z^+)\right.$$ ($\lfloor x\rfloor$ = largest integer not exceeding $x$) I am very bad as English and ...
-2
votes
3answers
423 views

Count the the number of elements in a set, exactly divisible by 2 out of 3 numbers

I need a hint to solve the following problem, in a way that a 10yr old child can understand. On a blackboard, all whole numbers from 1 to 2006 were written. John underlined all numbers divisible by ...