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

learn more… | top users | synonyms

-3
votes
0answers
31 views

9-by-9 filled, magic square

Construct a 9-by-9 filled, magic square using the integers from 0 to 80. The magic square should additionally have the property that when it is divided into ninths, each 3-by-3 subsquare is also ...
1
vote
1answer
36 views

Defining a new operation (From the International Mathematical Tournament of the Towns)

An operation denoted by * defines, for each pair of numbers (x, y), a number x * y such that for all x, y and z the following identities hold: x * x = 0; x * (y * z) = (x * y) + z Where + denotes ...
1
vote
0answers
33 views

4-by-4 regular square in decimal and base-4

We can say that an $n$-by-$n$ square is regular provided that: Each of the integers from $0$ to $n^2 − 1$ appears in exactly one cell, and each cell contains only one integer (so that the square is ...
0
votes
1answer
19 views

If N,E & T are distict positive integers such that …

I am stuck with the following problem that says: What I see that $2013=3 \times 11 \times 61$ . So, one possible sum of N,E & T is $ \,\,3 +11 +61=75$ . I am not sure what to do next as none ...
2
votes
1answer
32 views

polynomials such that $P(k)=Q(l)$ for all integer $k$

In a book I have read this problem: Given $P\in \mathbb{R}[X]$, if $P(X)$ takes at every integer, a value which is the $k$-th power of an integer, then $P(X)$ itself is the $k$-th power of a ...
2
votes
1answer
26 views

proofs of $n\sum_{d|n}\frac{(-1)^{d+1}}{d}=\sum_{d|n,d \text{ odd}}d$

I'm looking for other proofs of the identity : For all integer $n\in \mathbb{N}^{+}$: $$n\sum_{d|n}\frac{(-1)^{d+1}}{d}=\sum_{d|n,d \text{ odd}}d $$ where in the first sums is taken over all ...
1
vote
2answers
67 views

How to evaluate $f(2^73^55^6)=?$

I am stuck on the following problem and do not know how to proceed: We define a function $f(N)=\text{ sum of digits of N,expressed as decimal number}$ e.g.$f(137)=1+3+7=11$. Then I have to ...
1
vote
1answer
25 views

Difference of the difference of consecutive squares

I was playing around with the square numbers and I noticed something: $$\left. \begin{array}{r} &\left. \begin{array}{r} &1^2 = 1\\ &2^2=4\\ \end{array} \right\} \ 3 \\ &\left. ...
1
vote
1answer
29 views

Order of $p$ in $\Bbb Z/(p^n-1)\Bbb Z^\times$ is $n$

In an answer here, it is said without proof that if $p$ is a prime and $n$ an integer, the order of $p$ in $(\Bbb Z/(p^n-1)\Bbb Z)^\times$ is $n$. I tried to prove that, and it boils down to the ...
3
votes
2answers
63 views

GCD of many numbers

Given $a_1,...,a_n$ $gcd(a_1,...,a_n) = b$ I need to find $i$, so if i apply euclids algorithm to $(a_1,a_i)$, i end with $(0,b)$ or $(b,0)$.
1
vote
1answer
34 views

Properties of square roots

Forgive me if this question is very basic, I don't know much about the properties of square roots. My goal is to compute the square root of a very large number (around 1024 bits). While toying around ...
2
votes
3answers
61 views

Number Theory : $\gcd$ of $(a^2 + b^2, a+b)$ , where $\gcd$ of $(a,b)$ $ = $ $1$?

I was solving some basic number theory problems when I came across : What is $\gcd(a^2 + b^2, a+b)$, where $a$ and $b$ are relatively prime integers that are not both $0$? Can someone help me ...
4
votes
2answers
56 views

Are zero and one relatively prime?

The definition of relative primality that I was taught was that: Two numbers are relatively prime if the only common positive factor of the two numbers is one. ...
5
votes
2answers
91 views

First k primes and unity

Divide the first $k$ primes into $2$ groups, such that the difference of their products is one/unity, i.e. $$3-2=1;\;\;\;\;\;\;2*3-5=1;\;\;\;\;\;\; 3*5-2*7=1$$ After these three $k=2$, $k=3$ and ...
2
votes
1answer
13 views

For an odd prime $p$, prove that the quadratic residues of $p$ are congruent modulo $p$ to the integers

For an odd prime $p$, prove that the quadratic residues of $p$ are congruent modulo $p$ to the integers $$1^2,2^2, 3^2,\ldots, \left(\dfrac{p-1}{2}\right)^2$$ I know Euler's criterion but not sure ...
0
votes
3answers
50 views

Proving gcd(a+b,a-b) >= gcd(a,b)

Prove that $gcd(a+b, a-b)\geq gcd(a,b)$. Right now am not seeing a way to approach this. here are the relevant relationships in the book: 1)$lcm(a,b)=ab/gcd(a,b)$ 2)$lcm(ab,ad)=a[lcm(b,d)]$
2
votes
3answers
74 views

Reduction of $\frac a{b +1}$

Can we convert $\frac a{b+1}$ into a fraction having only $b$ as a denominator? What are the steps in doing so?
0
votes
2answers
26 views

Lowest common multiple with a fixed

Let's say we have $a,b >0 $, $a>b$ and $b>c$ can we determine if $gcd(a,b)$ is greater than or less than $gcd(a,c)$? More generally, how would a graph of $gcd(a,x)$ look?
2
votes
4answers
50 views

How does one show that for $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd.

For $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd. Firstly, $k \geq 1$ I can see induction is the best idea: Show for $k=1$: $2^{2^1} + 5 = 9 , 2^{2^1} + ...
1
vote
3answers
90 views

Why does $5x^2+6xy+2y^2=2yz+z^2$ have no integer solutions?

Why does $5x^2+6xy+2y^2=2yz+z^2$ have no primitive integer solutions? Modulo $2$ says that $x$ and $z$ are odd. Modulo $3$ says that $x=0 \bmod 3$ and $y=-z \bmod 3$. I cannot get anything modulo $5$. ...
2
votes
2answers
106 views

Changing the Modulo congruence base?

This is a conversion someone on SE made: $$77777\equiv1\pmod{4}\implies77777^{77777}\equiv77777^1\equiv7\pmod{10}$$ But I don't understand how this is done?
0
votes
2answers
88 views

Fibonacci number, combinatorics , fractions [closed]

Let $F_1 = F_2 = 1$ and $F_{n-1} + F_n = F_{n+1}$, Count and simplify $ \frac{1}{2} * nC1 *F_1 + \frac{2}{3} * nC2 *F_2 + \frac{3}{4} * nC3 *F_3 + \cdots + \frac{n}{n+1} * nCn *F_n $ Edit : I dont ...
3
votes
2answers
96 views

Find the last digit of $77777^{77777}$

Find the last digit of $$77777^{77777}$$ I got a pattern going for $77777^n$ for $n=1, 2, ....$ to be: $$7, 9, 3, 1$$ for $n = 1, 2, 3, 4$ respectively. The idea is: $$77777^{77777} \pmod{10}$$ ...
-1
votes
1answer
24 views

Proof involving inverses and modulo

I'm working through an exercise which states: Let a' be the inverse of a modulo m and let b' be the inverse of b modulo m. Prove that a'b' is the inverse of ab modulo m. So far what I have is: We ...
1
vote
0answers
33 views

number theory proof involving fibonacci number [duplicate]

Problem: Prove that $$ \binom{n}{1}F_1+\binom{n}{2}F_2+\binom{n}{3}F_3+\cdots+\binom{n}{n-1}F_{n-1}+F_n=F_{2n}, $$ where $F_n$ denotes the $n$th Fibonacci number. I tried induction, but I didn't ...
2
votes
1answer
44 views

Number Theory : Primes not in Twin Primes

I was working through some basic number theory questions , when I came across : Show that there are infinitely many primes that are not one of the primes in a pair of twin primes How can I go ...
-2
votes
1answer
35 views

Recovering the coefficients $b_r$ of the binomial sum $\sum_{r=0}^n\binom{n}rb_r$ [closed]

Suppose that the sequences of real numbers $a_0,a_1,a_2,a_3,\ldots$ and $b_0,b_1,b_2,b_3,\ldots$ satisfy the relation $$a_n=\sum_{r=0}^n\binom{n}rb_r\;.$$ Then prove that ...
1
vote
2answers
20 views

Proof dealing with greatest common divisors

I'm working on a proof which concludes that if $a\equiv b (mod\ m)$ then $gcd(a,m) = gcd(b,m)$ I know that we can rewrite the congruence as $km = a-b$ for some $k \in \mathbb{Z}$ I rearranged the ...
4
votes
3answers
241 views

Divisibility by a prime number p.

Show that the cube of a number is divisible by a prime p then the number is divisible by p. Here is my attempt so far: Call the number x. Then from the definition of divisibility, we can say ...
0
votes
1answer
35 views

Euler phi Function and Floor Function

Let $\phi(x)$ be the euler phi function and $\lfloor x\rfloor $ is floor function Count the sum of $ \phi(1)\cdot\lfloor \frac{2015}{1} \rfloor + \phi(2)\cdot\lfloor \frac{2015}{2} \rfloor + ...
0
votes
1answer
15 views

Clarification on the definition of a Primitive Root?

So I was given the following definition: If $ord_m(a)= \phi(m)$, then we call $a$ a primitive root modulo $m$. I am wondering if this definition applies in an "if and only if" sense. That is, is: ...
9
votes
5answers
949 views

Number Theory : Infinitude Of Primes - a different proof

I was doing some basic Number Theory problems and came across this problem : Show that the integer : $Q_{n} = n ! + 1$, where $n$ is a positive integer, has a prime divisor greater than $n$. ...
0
votes
1answer
39 views

prove that an integer a is odd if and only if it can be written as a sum of two consecutive integers

Can someone please revise my proof. (->) Let $a$ and $x$ be arbitrary integers. Assume $a$ is odd so there exists an integer $k$ s.t $a = 2k + 1$. $a = 2k + 1 = k + k + 1= k + (k+1)$ , evidently ...
6
votes
1answer
199 views

Divisibility property proof: If $e\mid ab$, $e\mid cd$ and $e\mid ac+bd$ then $e\mid ac$ and $e\mid bd$.

$a,b,c,d,e\in \mathbb{Z}$. Prove that if $e\mid ab$, $e\mid cd$ and $e\mid ac+bd$ then $e\mid ac$ and $e\mid bd$. I could use some hints on how to prove this property.
8
votes
4answers
133 views

$k$ with an even sum of digits for all multiples of $k$?

Is there a number $k\in\mathbb{N}$ such that $k\cdot n$ has an even sum of digits for all $n\in\mathbb{N}$? I would be grateful for any ideas of how to attack this problem...
-1
votes
1answer
82 views

Show that $\sqrt{2} + \sqrt{3} +\sqrt{5}$ is an irrational number. [closed]

Show that $\sqrt{2} + \sqrt{3} +\sqrt{5}$ is an irrational number.
0
votes
2answers
48 views

Elementary number-theory proof sought

Take any 8 3-digit numbers $\in \mathbb Z^+$. There will always be at least two of them which you can put next to eachother to form a 6-digit number which is divisible by 7. Why?
1
vote
1answer
57 views

Number Theory : Primes that are the difference of the fourth powers of two integers

I was doing some basic Number Theory problems and came across this problem : Find all primes that are the difference of the fourth powers of two integers How can I go about it ?
-3
votes
2answers
36 views

Number system and square roots [closed]

If $n^2 + 96$ is a perfect square then number of possible values of $n$ is (where $n$ is natural number). (a) $3$ (b) $ 4$ (c) $6$ (d) $8$
2
votes
2answers
59 views

Infinitely many primes of the form $4n - 1$ proof [duplicate]

Prove that there are an infinite number of primes of the form $4n - 1$. I am having trouble solving this problem, so any help would be appreciated.
0
votes
0answers
25 views

Can i from the Smith Normal Form conclude which Rows are Linear Dependend?

If i have calculated for an integer matrix A: $$A = V*S*T$$ So that S is Smith Normal form, and V,T, are unimodular matrixes. The rank of S is equal to the rank of A. Can i somehow decide which ...
4
votes
1answer
84 views

Number Theory : If $a^{n}-1$ is prime then $a=2$ and $n$ is prime?

I was doing some basic Number Theory problems and came across this problem : Show that if $a$ and $n$ are positive integers with $n\gt 1$ and $a^{n} - 1$ is prime, then $a = 2$ and $n$ is prime ...
1
vote
1answer
29 views

Solve the quadratic congruences, or show them to be unsolvable.

Solve the following congruences, or show them to be unsolvable: $(a) 3x^2 - 5x +7 \equiv 0 \mod 13$ Since $9 \cdot 3 \equiv 1 \mod 13$, $9 \cdot 5 \equiv 6 \mod 13$ and $9 \cdot 7 \equiv 11 \mod ...
1
vote
0answers
60 views

Number Theory : Do integers $s$ and $t$ exist?

I was solving some basic number theory problems from Number Theory by Rosen and was stuck on the following exercise problem : Show that if $a$ and $b$ are odd positive integers and b does not ...
4
votes
0answers
23 views

Characterization of Extended Lucky Numbers

The Lucky Numbers is a sieve where one starts out with the positive integers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ... and then eliminate ...
2
votes
1answer
47 views

$1 + \frac {1}{2}+\frac {1}{3} +… +\frac {1}{p-1} = \frac {a}{b}$, prove that $a$ is divisible by $p$.

If $p$ is an odd prime and if $1 + \frac {1}{2}+\frac {1}{3} +..... +\frac {1}{p-1} = \frac {a}{b}$, where, $a,b$ are positive integers, prove that $a$ is divisible by $p$. I found this exercise in a ...
1
vote
2answers
52 views

Solve equation in $\mathbb{Z}_{13}$ without brute-force

Find all solutions to $x^3 = 7$ in $\mathbb{Z}_{13}$ using theory and not brute-force. I dont know how to proceed, I used brute-forced but dont know what kind of theory to use otherwise.
2
votes
3answers
47 views

Even number sum proof

Prove that every even number $k\geqslant 8$ can be represented as $m,n\in \mathbb{N}\setminus \{1\}$ $$k=m+n$$ and $\gcd(m,n)=1$. I was able to do it, if $k$ is an odd number but not if it is even. I ...
1
vote
0answers
63 views

Can this approach to showing no positive integer solutions to $p^n = x^3 + y^3$ be generalized?

The following problem is a $2000$ Hungarian Olympiad question. Find all primes $p$ such that: $$p^n = x^3 + y^3$$ The answer is that there are only $2$ solutions: $2^1 = 1^3 + 1^3$ $3^2 = 2^3 + ...
0
votes
1answer
42 views

Integers $d$ for which the Negative Pell equation is soluble for both $d$ and $2d$?

Let $\text{NPE}_d$ denote the negative Pell equation: $$ x^2-dy^2=-1$$ Where $d$ is a given positive nonsquare integer and integer solutions are sought for x and y. we know that (in this paper): ...