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

learn more… | top users | synonyms (1)

1
vote
1answer
33 views

Olimpic's Problem about Theory of numbers.

Let $Y=\{1,2,\ldots, 2014\} \subset \mathbb{N}$. Find the maximal subset $A\subset Y$ such that, $\forall x\in A$, $x\not\mid\sum_{y\in A\setminus\{x\}}y$. Example, $A'=\{2,4,6,\ldots,2014\}\cup\{5\}$...
0
votes
0answers
19 views

Is incorrect the demonstration Landau?

Leon Henkin says, at the end of his On Mathematical Induction text, Edmund Landau failed to demonstrate the existence and uniqueness of adding natural numbers, because ignored axioms P1 and P2 of ...
0
votes
0answers
14 views

Elliptic curve, different forms of.

y^2 = x^3 + mx + c An elliptic curve in the form defined in Wikipedia y^2 = x(x-A)(x+B) = x^3 +(B-A)x^2 + ABx Frey's curve has no term in x^2, but 2. does because from Fermat, A=a^n not equal ...
2
votes
5answers
56 views

Prove that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1$

Let $a$ and $b$ be two odd positive integers. Prove that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1$. I tried rewriting it to get $\gcd(2^{2k+1}+1,2^{\gcd(2k+1,2n+1)}-1)$, but I didn't see how this helps.
36
votes
9answers
19k views

Prove that $\sqrt 2 + \sqrt 3$ is irrational

I have proved in earlier exercises of this book that $\sqrt 2$ and $\sqrt 3$ are irrational. Then, the sum of two irrational numbers is an irrational number. Thus, $\sqrt 2 + \sqrt 3$ is irrational. ...
1
vote
1answer
25 views

Remainder modulo matrices.

Is it possible to have a consistent definition of $A\bmod_{left} B$ that respects matrix multiplication from left where $A$ and $B$ are two square matrices with non-negative entries? Is there a ...
12
votes
1answer
166 views

Arrange Relatively Prime Numbers in a Circle

The question: In how many ways can you arrange the numbers $1$ to $8$ in a circle so that neighboring numbers are relatively prime? Can you generalize for $1$ to $n$? It's fairly easy to list ...
1
vote
0answers
24 views

Derivation of Frey equation from FLT

I understand, on a layman's level, Fray's motivation to write an elliptic equation corresponding to an assumed solution to FLT. My question is, how technically is Frey's equation derived? Where did ...
0
votes
4answers
44 views

Prove $3\mathbb{Z}+1=\{6\mathbb{Z}+1\}\cup\{6\mathbb{Z}+4\}$

I was wondering if someone could confirm I have proven the following equality correctly. Also, for part II should I have let $n\in \mathbb{Z}$ as opposed to $n\in 6\mathbb{Z}+1$ or was I correct? ...
0
votes
5answers
82 views

find $u,v\in \mathbb Z$ such that $231u+45v=1$.

I have to find $u,v\in \mathbb Z$ such that $231u+45v=1$. By Euclide algorithm, \begin{align*} 231&=5\cdot 45+6\\ 45&=6\cdot 7+3\\ 7&=3\cdot 2+1 \end{align*} The first equation gives $$6=...
5
votes
0answers
33 views

Numbers on a circle: how many arc sums can be positive?

There are $n$ real numbers, $a_1,\dots,a_n$, arranged on a circle. Given a fixed integer $k<n$, let $S_i$ be the sum of the $k$ adjacent numbers starting at $a_i$ and counting clockwise, like this (...
3
votes
0answers
64 views

Continued fraction $1 + \frac 2{3 + \frac 4 {5 + \cdots}} = \frac 1 {\sqrt{e} - 1}$?

I saw this link (written in Japanese) and found an interesting problem: Calculate $1 + \frac 2{3 + \frac 4 {5 + \cdots}}$. The link provides the answer ($\frac 1 {\sqrt e - 1}$) and a hint that one ...
-1
votes
0answers
32 views

The order of the group $U(n)$ is even for $n\gt2$ [on hold]

Use the corollary to Lagrange's theorem that the order of an element in a group $G$ divides the order of the group $G$ to prove that the order of $U\left ( n \right )$ is even when $n\gt2.$ I ...
3
votes
2answers
91 views

If $x\in\mathbb R$, solve $x^{\lfloor x\rfloor}=\frac{9}{2}$, where $\lfloor x\rfloor$ is the integer part of $x$.

If $x\in\mathbb R$, solve $x^{\lfloor x\rfloor}=\frac{9}{2}$, where $\lfloor x\rfloor$ is the integer part of $x$. Of course, $x=\lfloor x\rfloor+\{x\}$, where $\{x\}$ is the fractional part of $x$. ...
0
votes
2answers
14 views

Claim $(\mathbb{N}, \leq)$ is a discrete space, but is $(-\infty, b)$ a subbasic element?

Let $\mathbb{N}$ denote the set of natural numbers, then a subbasis on $\mathbb{N}$ is $$S = \{(-\infty, b), b \in \mathbb{N}\} \cup \{(a,\infty), a \in \mathbb{N}\}$$ Let $\leq$ be the relation on ...
1
vote
0answers
59 views

Are complex numbers complete in every way?

I was told many times a story. Indeed a fascinating one to me as a student learning mathematics. First there were natural numbers. People started adding things and finding solutions to finding the ...
6
votes
1answer
98 views

Prove or disprove that $2^n$ divides $T_{2^n}$ for $n > 2$.

The Tribonacci sequence satisfies $$T_0 = T_1 = 0, T_2 = 1,$$ $$T_n = T_{n-1} + T_{n-2} + T_{n-3}.$$ Prove or disprove that $2^n$ divides $T_{2^n}$ for $n > 2$. (I think $2^n$ divides $T_{2^n}$...
2
votes
1answer
54 views

Integer Solutions to an Ellipse

I'm trying to find positive integer solutions to the ellipse $$x^2 - xy + y^2 - k^2 = 0$$ where $k$ is a constant. Specifically, I already have two solutions for a given $k$, and I'm trying to find a ...
1
vote
2answers
46 views

If $ n = a b $ and $ a < b $, show that $ a < \sqrt{n} $.

For an integer $n\ge 2$, suppose that $n = ab$, where $a, b$ are integers and $a \le b$. Prove that $a\le \sqrt{n}$ For $a=b$, $n=a*a=a^2$ and $\sqrt{n}=\sqrt{a^2}=a\le a$ which is true since $a=a$. ...
0
votes
0answers
36 views

A divisibility conjecture related to the Ramanujan-Nagell equation

The Ramanujan-Nagell equation is $$ x^2+7=2^n, $$ where it has been proven (using non-elementary methods) that the complete solution is $n \in \{3, 4, 5, 7, 15\}$. I've found an elementary way to ...
3
votes
1answer
36 views

Proving a number is Carmichael

here is my question: Let $p>3$ be prime, s.t $q = 2p-1$ and $g = 3p-2$ are primes as well. (For example $p=19$,$13$,$7$). Prove that $N = pqg$ satisfies $p-1|N-1$, $q-1|N-1$ and $g-1|N-1$. I ...
0
votes
1answer
28 views

Calculating the last digit of exponent

I need to calculate the last digit of $723^n$.(For every positive integer $n$). If it was to calculate the last digit of $a^b$ when I know the value of $a$ and $b$,then it was easy- for example,If I ...
12
votes
1answer
430 views

If $p$, $q$ are naturals, solve $p^3-q^5=(p+q)^2$.

In If $p,q$ are prime, solve $p^3-q^5=(p+q)^2$., the author asks to solve the equation $p^3-q^5=(p+q)^2$ for primes $p$ and $q$. A proof is given that $p=7, q=3$ is the only solution. In this "...
1
vote
1answer
25 views

Proof about rational roots and polynomials

Show that if $a$, $b$ and $c$ are all integers and $\xi = m/n$ is a rational solution of the equation $$x^3 + ax^2 + bx + c = 0 $$ then $\xi$ is an integer. Hints: (i) You may assume that $\gcd(m, n) ...
9
votes
0answers
341 views

Power Diophantine equation involving primes: $(p+q)^q-p^q-q^q+1=n^{p-q}$

Suppose $p$ and $q$ are prime numbers, and $n>1$ is a positive integer. Find all solutions to the following Diophantine equation:$$(p+q)^q-p^q-q^q+1=n^{p-q}$$ What I have tried: Obviously $p>q$...
0
votes
3answers
54 views

Prove If $n\in\mathbb{N}$ is not even then $\exists$ $k\in \mathbb{N}$ s.t. $n=2k-1$

I was told to do a proof by contradiction and I am not sure if what I came up with is valid if you can confirm or assist me I would greatly appreciate it. Prove If $n\in\mathbb{N}$ is not even ...
0
votes
1answer
14 views

A primality test using the gcd

Let $f:\mathbb{N} \rightarrow \mathbb{N}$ be defined by $$f(n) = gcd(n,\lfloor \sqrt{n}\rfloor ! \mod n).$$ Show that a) If $p$ is a prime divisor of $n$ with $p \leq \sqrt{n}$, then $p \mid f(n)...
2
votes
1answer
39 views

Question about Diophantine equations

When Mr. Smith cashed a check for x dollars and y cents, he received instead y dollars and x cents and found that he had two cents more than twice the proper amount. For how much was the check written?...
1
vote
2answers
52 views

Calculating the gcd of complex numbers

I need help in calculating the gcd of complex numbers For Example: $\gcd(3+i,1-i)$. The problem is,I don't even know what's the algorithm for complex numbers...
1
vote
1answer
66 views

Does this wrong cancellation of $B$ work for $\overline{AB}/ \overline{BC}=A/C$?

My teacher says that wrong cancellation of $B$ for the fraction$$\frac{\overline{AB}}{\overline{BC}}=\frac{A}{C}$$ will work for some numbers. I see some trivial cases when $A=B=C$, but are there ...
3
votes
0answers
41 views

How to prove $(\{2^n3^m\alpha\})_{m,n\in\mathbb{N}}$ is dense in [0,1]?

$\forall \alpha\in [0,1]\setminus\mathbb{Q}$, how to prove $(\{2^n3^m\alpha\})_{m,n\in\mathbb{N}}$ is dense in [0,1]? $\{x\}$ is the fractional part of x. Any hint would be appreciated!
0
votes
1answer
79 views

AMC 2012 Junior Question [on hold]

$x^2 +y^2 +z^2 = 100x+10y+z $. Find the smallest number and largest number that fit the equation.The numbers are below 1000 I am just baffled at the question.Is there a way to tackle such questions?
-5
votes
0answers
39 views
3
votes
0answers
31 views

Decomposition of quotient group of lattices

By the Chinese remainder theorem, we know that $\mathbb{Z}_m \cong \prod_{i=1}^l \mathbb{Z}_{p_i^{k_i}}$, where $m=p_1^{k_1} ... p_l^{k_l}$. Now, let $\Lambda = A(\mathbb{Z}^n) \subseteq \mathbb{Z}^...
3
votes
0answers
64 views

Sine identity involving (3/p) for prime p greater than 3.

I am working through Ireland and Rosen's "Classical Introduction to Modern Number Theory" and am very stuck on this problem (#34 in Chp 5, 2nd edition): Note that $(a/b)$ is the Legendre symbol (or ...
0
votes
2answers
38 views

Proof about diophantine equation

show that the diophantine equation $$x^2-y^2=N$$ is solvable in nonnegative integers x and y if and only if N is odd or divisible by 4. Show further that the solution is unique if and only if $|N|$...
0
votes
2answers
28 views

proof about rational roots test theorem

show that if the reduced fraction a/b is a root of the equation $$c_0x^n+c_1x^{n-1}+...+c_n=0$$ where x is areal variable and $c_0,c_1,....,c_n$ are integers $c_0\neq 0$ then $a|c_n$ and $b|c_0$ ...
2
votes
5answers
70 views

Prove that $pq$ is not expressible in the form $px+qy$

Let $p$ and $q$ be distinct primes. Prove that $pq$ is not expressible in the form $px+qy$ where $0 \leq x \leq q-1$ and $0 \leq y \leq p-1$. Similarly prove that $pq-p-q$ is not expressible in that ...
2
votes
0answers
87 views

Why it is impossible for primitive Pythagoras triplets in integers to be all as powerful numbers?

I had seen an elementary proof for Fermat's last theorem at Quora. I had checked all the steps (around one page only),where I couldn't catch any error, but I was confused about the last step only ...
2
votes
3answers
79 views

Q27 from AMC 2012(Senior)

Five consecutive integers $p,q,r,s,t$,each less than $10000$, produce a sum which is a perfect square,while the sum of $q,r,s$ is a perfect cube.What is the value of $ \sqrt{p+q+r+s+t}$ ? What I have ...
6
votes
2answers
105 views

Show that an integer matrix with following conditions is the identity $I$

every entries of $A$ is integer every entries of $A-I$ is multiple of a prime $p$ ($p\geq3$) there exists $n\ge1$ such that $A^n=I$ show that $A=I$ I tried $A=I+p^kB$ where not every entries of $B$ ...
0
votes
1answer
26 views

Contrapositive, Negation, and Converse of statements

I am having trouble with the wording of these statements particularly the negation statement. Is that the best way to put it or could you provide a better alternative? Also for the converse proof ...
3
votes
2answers
95 views

Q26 from AMC 2012

Slim took a long road trip across Australia over a number of days($x>1$).She travelled a total of 2012 km.On the first day,she travelled a whole number of kilometers and each subsequent day she ...
2
votes
5answers
289 views

$33^{33}$ is the sum of $33$ consecutive odd numbers. Which one is the largest? (Q25 from AMC 2012)

The number $33^{33}$ can be expressed as the sum of $33$ consecutive odd numbers. The largest of these odd numbers is $\mathrm{A.}\ 33^{32} +32$ $\mathrm{B.}\ 33^{31} +32$ $\mathrm{C.}\...
5
votes
1answer
61 views

On “good” numbers and $m \times n$ real matrices

Let $m,n > 1$ be odd integers. Different real numbers are written in the cells of the $m \times n$ table ($m$ rows and $n$ columns). The number is called "good" if 1) It is the largest in its ...
2
votes
2answers
77 views

$n=a^2-b^2$ iff $n \not\equiv 2(\mathrm{mod\ }4)$

I have to show that $n=a^2-b^2$ iff $n\not\equiv 2$ (mod $4$). Where $a$, $b$ are integers. I already got the explicit $(a,b)$ if $n\not\equiv 2$ (mod $4$). However, I am stuck with the other ...
3
votes
1answer
212 views

Working with least absolute remainders in the Euclidean Algorithm (possible typo)

I'm reading Burton's Elementary Number Theory (4th edition). On page 29, we read, "The number of steps in the Euclidean Algorithm usually can be reduced by selecting remainders $|r_{k+1}|<r_k/2$." ...
2
votes
1answer
72 views

Number Theory relating Perfect Squares

Find all the possible positive integral values of $n$ for which $n+9$, $16n+9$ and $27n+9$ are all perfect squares. I didn't work on it as I have no idea on how to approach such question. I only ...