Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

2
votes
0answers
54 views

Is this proof of a mathematical olympiad problem correct?

I'm quite sure about the exactness of my proof, but I'd like to hear (constructive) criticism about my writing. This is the problem: Every non-negative integer is coloured white or red, so that: 1) ...
1
vote
1answer
59 views

Diophantine Equation: $a^3=a(b^2+c^2+d^2)+2bcd$

Let $a,b,c,d\in \mathbb{Z}$. Solve $$a^3=a(b^2+c^2+d^2)+2bcd$$ I've tried everything but I haven't been able to find a general solution. Note: We may assume $\gcd(a,b,c,d)=1$ because of homogeneity. ...
2
votes
1answer
37 views

Checking the IBAN and dividing large numbers mod 97. Why does it work?

What's the reason (or is there an easy explanation) of why it is possible to calculate the division mod $97$ of a large number by first calculating it for the first $9$ (or $6$?) leftmost digits and ...
3
votes
3answers
38 views

Find all the positive integers $m$ such that $p_{m}≥2m$

Find all the positive integers $m$ such that $$p_{m}≥2m$$ where $(p_{m})$ is the sequence of prime numbers I have no idea to start.
-1
votes
1answer
45 views

Basic elementary number theory [duplicate]

I just enrolled in a class called "Elementary Number Theory" and I am left confused in every class due to the different notations and proofs shown. Is there a really basic book on Number Theory out ...
1
vote
4answers
65 views

when exactly does $711 \equiv \alpha \times 2015 \mod 1302$ have a solution?

I know this is quite a stupid question, but I just can't figure out whether or not $$711 \equiv \alpha \times 2015 \mod 1302$$ has a solution for $\alpha \in \mathbb{Z}$. In my eyes, 2015 and 1302 ...
0
votes
2answers
39 views

Find the digit using the given conditions [closed]

$N$ is a $50$ digit number (in the decimal notation). All the digits except the $26$th digit (from the left) are $1$. If $N$ is divisible by $13$, find the $26$th digit.
-1
votes
1answer
63 views

give direct proof of the fact $a^2 - 5a + 6$ is even for any integer [duplicate]

I know this is true but I don't know how to prove it. I have worked it out for the integers from $1$ to $10$ but this is not direct proof, is there a formula I need?
3
votes
2answers
157 views
+50

A natural number $n>2$ is a prime iff $\prod_{k=1}^{n-1} k \equiv n-1 \pmod {\sum_{k=1}^{n-1} k}$

Is this proof acceptable ? Theorem 1 (Wilson). A natural number $n>1$ is a prime iff: $$(n-1)! \equiv -1 \pmod n.$$ Theorem 2. A natural number $n>2$ is a prime iff: ...
0
votes
3answers
57 views

Can someone calculate with modulo calculator? [closed]

Can someone show me how to calculate this one, Im having a little trouble. Thanks guys. $$123^{12}\equiv\;?\pmod{11}$$
2
votes
5answers
106 views

Testing integrality of a number

Let $x$ be a real number. Show that $x$ is an integer if and only if $$[x] + [2x] + \cdots + [nx] = n ([x] + [nx])/2,$$ for all natural numbers $n$. Can you give me an idea?
-1
votes
1answer
39 views

Division of natural numbers [duplicate]

How can I prove that $9|n$ if and only if $9$ divides the sum of the digits of $n$, where $n \in \mathbb{N}$
0
votes
1answer
29 views

Prime dividing multinomial [closed]

Let $p$ be a prime. I was wondering for what numbers $a_1,\ldots,a_p$ such that $a_1 + \ldots + a_p = p$ that $p\mid\binom{p}{a_1,\ldots,a_p}$?
2
votes
1answer
18 views

solvability of $r^x \equiv a \pmod {n}$

$r^x \equiv a \pmod {n}$ Is it correct to say this congruence is solvable if and only if $\gcd(a,n) = 1$ ? I am looking for a proof or intuitive argument for making sense of this. Thanks in advance! ...
3
votes
6answers
63 views

Why Are There No Solutions To $2^x \equiv 3\pmod{9}$?

I know this congruence has no solutions because $\gcd(3,9) \ne 1$. I would like to understand why this gcd restriction is needed for solvability. Thanks!
3
votes
5answers
72 views

Show that if $a$ is an integer, then 3 divides $a^3 - a $

Show that if $a$ is an integer, then 3 divides $a^3 - a $ we can write, where $k$ is an integer; $a^3 - a = 3k $ $a(a^2 - 1) = 3k $ Now if $a = k$ then $a^2 -1 = 3$ and $a= \pm2 $ so $ a^3 - a = ...
2
votes
0answers
28 views

What is the meaning of this question?

Exercise: Consider the question of representing integers with the base a . In order to name the integers in this system we need words for the digits 0, 1, · · ·, a –1 and for the various powers of a: ...
4
votes
2answers
46 views

Prove that $89|2^{44}-1$

Is there any easier (less no. of steps or calculations) proof for this using congruences: $89|2^{44}-1$. My proof: $$2^6\equiv-25\mod89$$ $$2^5\equiv32\mod89$$ Now square both equations: ...
2
votes
1answer
31 views

Proving the existence of a bijection between $U_{mn}$ and $U_m \times U_n$ where $(m,n)=1$ , there by proving Euler $\phi$ is multiplicative

Without proving before hand that Euler's phi $(\phi)$ function is multiplicative , can we prove that there is a bijection between $U_{mn}$ and $U_m \times U_n$ , for any pair of relatively prime ...
2
votes
0answers
43 views

Prove there are no solutions to the equation $k(2^n-1)=(3^{2q+1}-1)$ where $n,q>1$.

Prove there are no solutions to the equation $k(2^n-1)=(3^{2q+1}-1)$ where $n,q>1$. For a start I reasoned that $n$ had to be odd as otherwise $3|2^n-1$ which was obviously bad. Furthermore, it ...
0
votes
1answer
30 views

Divisiblity of $n$ with $a,b,c$ is relative prime to p

Given an arbitrary prime $p > 2011$. Prove that there exist positive integers $a,b,c$ such that there exists some numbers from $a, b, c$ that are relatively prime to $p$, and for all positive ...
2
votes
3answers
94 views

Prove that if $p$ and $q$ are distinct primes such that $pq\mid n^2$ then $pq\mid n$.

Prove that if $p$ and $q$ are distinct primes such that $pq\mid n^2$ then $pq\mid n$. My Attempt: Assume that $pq\nmid n$. If $pq\nmid n$, then $p\nmid n$ or $q\nmid n$. Without loss of generality, ...
0
votes
1answer
28 views

Why do some other people say do for $12$, gro for $144$, and mo for $1,728$ when they use base $12$?

I heard on YouTube that do is some people's word for $12$ in the duodecimal system, but they also say gro for $144$ because it's a gross ($12$ dozens) and mo for $1,728$. I think it's amazing, but ...
0
votes
1answer
34 views

Why do some other people use dek and el rather than letters as the eleventh and twelfth digits in the dozenal or duodecimal system?

I've noticed on a YouTube video titled Base $12$ - Numberphile that some other people who use the duodecimal system use dek and el for the eleventh and twelfth digits. I know for one thing that them ...
0
votes
2answers
27 views

Prove that if the sum of digits of a number is divisible by 3, so is the number itself.

Here is the proof of the converse: Iff a number $n$ is divisible by $3$, then the sum of its digits is also divisible by $3$. Proof: We know $n \mod 3 = 0$. By the basis representation theorem, $n$ ...
8
votes
1answer
100 views

Division with Gaussian integers

If we are given $A = 7 - 3i, B = 4 + 3i$ and suppose we need to find Gaussian integers $Q, R$ such that $A = QB + R$ with $N(R) < N(B)$ and $N(a + bi) = a^2 + b^2$. OK, so I did the division ...
2
votes
1answer
27 views

Infinite intersection between a arbitrary set of integers and a set of floor powers

Let $E$ be an infinite set of positive integers, proves that there is a $\alpha \in \mathbb{R}$ such that $\{\left \lfloor \alpha^k \right \rfloor ;k \in \mathbb{N} \}\cap E$ is infinite. I have two ...
1
vote
4answers
72 views

Finding 3 variables a,b,c. 31a+30b+28c=365

well, I have this question: Find positive integers $a,b,c$ that solve $$31a+30b+28c=365.$$ Well, it was easy to find them, since i noticed that it actually asks for the months in a year. As, how many ...
1
vote
2answers
48 views

Fermat Numbers Proof [duplicate]

Fermat numbers are shown by: $F_m = 2^{2^m} + 1$. How can I prove that for any $m ≠ n$, I can have $(F_m, F_n) = 1$?
1
vote
3answers
40 views

Set of Numbers with GCD equal to $1$

Can someone give me a set of $4$ positive integers with $3$ of them having a common divisor that is greater than $1$, but the GCD of all four positive integers is $1$.
2
votes
3answers
44 views

Number theory: prove that if $a,b,c$ odd then $2\gcd(a,b,c) = \gcd(a+b,b+c, c+a)$ [closed]

Please help! Am lost with the following: Prove that if $a,b,c$ are odd integers, then $2 \gcd(a,b,c) = \gcd( a+b, b+c, c+a)$ Thanks a lot!!
0
votes
1answer
35 views

Permutations and Combinations Olympiad

Suppose that all positive integers which are relatively prime to 105 are arranged in an increasing sequence - a1 , a2 ,a3 ,.... Evaluate a1000.
0
votes
0answers
54 views

Any conjecture connecting almost $k$-primes and $k$-partitions

Is there any conjecture or similar that suggests that almost $k$-prime can be partitioned into $k$ terms of which $k-1$ are composite and one prime or $k-2$ are composite and 2 prime?
0
votes
0answers
28 views

Evaluating GCD, LCM expression plugging different numbers to get a certain number - where should I stop?

Here's a computer science problem I'm trying to solve: Given an expression tree: type expr = | GCD of expr * expr | LCM of expr * expr | Number of int ...
1
vote
0answers
36 views

Methods for evaluating polynomials quickly

I am wondering what methods exist for effectively evaluating polynomials (manually or in the head) in a quick, efficient fashion. For example, one of my favorite methods is the "nested form of a ...
5
votes
0answers
118 views

Primes as sum of squares.

If $p_{i}$ and $p_{j}$ are two primes of the form $4k+1$ , with $p_{j} > p_{i}$, show that if $p_{j} \neq$ sum of two squares $p_{i}$ is also not equal to sum of two squares. It is well ...
4
votes
3answers
134 views

True or False: $2^{2^{2011}} \text{ divides } 2^{2^{2012} }$

True or false: $$2^{2^{2011}} \text{ divides } 2^{2^{2012} }$$ Give your justifications. I don't know how to start this problem so far. But, I guessed like this, $$2^{\underbrace{2\times ...
0
votes
2answers
34 views

Solve $x^3-ax=by$ If $\gcd(x,y)=1$

Solve the diophantine $x^3-ax=by$ If $\gcd(x,y)=1$. Any hint? My first impression is $\gcd(x,b)>1$ and $x^2=ky+a$ for some integer $m$. I conclude that as long as there exists a square integer ...
0
votes
1answer
44 views

Show that the set $S = \{ax + by : x, y ∈ \mathbb{Z} \} \cap \mathbb{N}$ is not empty

(a) Show that the set $S = \{ax + by : x, y ∈ \mathbb{Z} \} \cap \mathbb{N}$ is not empty. Proof. Notice that if $ a = b = 0$, then $S = \emptyset$, so pick an $a \ne 0$. If $a$ is positive, then ...
3
votes
3answers
285 views

Pythagorean triples

So I am given that $65 = 1^2 + 8^2 = 7^2 + 4^2$ , how can I use this observation to find two Pythagorean triangles with hypotenuse of 65. I know that I need to find integers $a$ and $b$ such that ...
0
votes
3answers
41 views

Help me answer this Number Theory question on GCD (involves exponents) [duplicate]

Basically I need a good hint how to solve the problem.I have solved it partly. $gcd(2^a-1,2^b-1)=2^{gcd(a,b)}-1$. I have reached till: $gcd(2^a-1,2^b-1)=gcd(2^{a-b}-1,2^b-1)$ How to ...
1
vote
3answers
50 views

If $\gcd (a,b) = 1$, what can be said about $\gcd (a+b,a-b)$?

Suppose $a, b \in \mathbb{Z}$, $a > b$, and $\gcd (a,b) = 1$. What can be said about $\gcd (a+b,a-b)$? Is it true in general that $\gcd (a+b,a-b) \leq 2$?
4
votes
2answers
58 views

Polynomial Diophantine Equation

If $x$,$y$ $\in \mathbb Z$, find all the solutions of $$y^3=x^3+8x^2-6x+8$$ I have tried factorizing the equation but the polynomial on $\text{R.H.S.}$ doesn't have any integral roots. ...
0
votes
1answer
37 views

Solving simultaneous linear congruences.

I'm struggling when solving the simultaneous linear congruences $$x\equiv 3 \pmod{101^{1000}}$$ and $$x\equiv 3 \pmod{7^{200}}$$ where the moduli are very large. I haven't got an issue when solving ...
0
votes
3answers
67 views

If a, b ∈ Z are coprime show that 2a + 3b and 3a + 5b are coprime.

If $a, b \in \mathbb{Z}$ are coprime show that $2a + 3b$ and $3a + 5b$ are coprime. My normal approach seems to get me nowhere.
15
votes
6answers
404 views

can a number of the form $x^2 + 1 $ be a square number?

I have been trying to prove that $x^2 + 1 $ is not a perfect square (other than $0^2 +1^2=1^2$). I'm stuck and can't move forward. The thing I have tried so is to relate the problem to a hyperbola ...
1
vote
0answers
36 views

sigma divisor function with gcd

For computational reasons, I want to show that the following holds true: Let $n_1,n_2,N\in \mathbb{N}$. One has $$ \sum_{a\mid \gcd(n_1,N)}\sum_{b\mid \gcd(n_2,\frac{n_1N}{a^2})} ab =\sum_{g\mid ...
6
votes
1answer
42 views

How many such triangles exist?

Let $ABC$ be a arbitrary triangle with integral sides such that the perimeter is $2006$. And one of the side $16$ times the other side. How many such triangles exist? Attempt
1
vote
0answers
38 views

Proving the Divisibility Rule for $3$ [duplicate]

Theorem: If 3 divides the sum of the digits of a number, then 3 divides that number
1
vote
1answer
27 views

Prove that any common divisor of $a$ and $b$ must also divide $m_0$.

I have already proven problem 1 but now that I am working on a different problem from a different set of questions. I am find that Problem 2 is asking for the same thing. I am understanding the ...