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

learn more… | top users | synonyms (1)

0
votes
0answers
6 views

Number of solutions to this nice equation $\varphi(n)+d(n^2)=n$

How many natural numbers $n$ satisfy the equation$$\varphi(n)+d(n^2)=n$$where $\varphi$ is the Euler's totient function and $d$ is the divisor function i.e. number of divisors of an integer. I made ...
1
vote
0answers
15 views

Lucas recurrence relation

Lucas recurrence relation is defined as: $V_n = PV_{n-1} – QV_{n-2}$; for $V_0 = 2; V_1 = P$ Here $P$ is positive integer and $Q = {-1, 1}$ or may be $+1$ or $-1$ A Fibonacci Pseudo prime with ...
0
votes
0answers
13 views

Devise a test for divisibility of an integer by 11, in terms of properties of its digits [duplicate]

Using the fact that $10 \equiv-1 \pmod{11}$, devise a test for divisibility of an integer by $11$, in terms of properties of its digits. Approach: Let the number with its digits $a_0\cdots a_n$ be ...
1
vote
2answers
30 views

Proof about congruence

Let $$f(x)=a_0x^n+a_1x^{n-1}+...+a_n$$ where $a_0,...,a_n$ are integers.Show that if d consecutive values of (i.e, values for consecutive integers) are all divisible by the integer d, then $d|f(x)$ ...
2
votes
2answers
64 views

I'm looking for a matrix $M$ with $\det(M)=a^2+b^2+c^2+d^2$

In order to show that $(a^2+b^2+c^2+d^2)(A^2+B^2+C^2+D^2)= \alpha^2+\beta^2+\gamma^2+\delta^2$ with $a,b,c,d,A,B,C,D,\alpha,\beta,\gamma,\delta \in \mathbb Z$. I would like to find a matrix with ...
1
vote
0answers
32 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 ...
2
votes
1answer
45 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
15 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
0answers
31 views

Prove that the decimal representation consists of exactly $k(m-k) + 1$ digits

For a positive integer $n$, let $6^{(n)}$ be the natural number whose decimal representation consists of $n$ digits $6$. Let us define, for all natural numbers $m$, $k$ with $1 \leq k \leq m$ $$\...
2
votes
5answers
58 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.
1
vote
0answers
26 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 ...
6
votes
0answers
36 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
69 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 ...
1
vote
0answers
61 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 ...
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
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 ...
0
votes
4answers
46 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? ...
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
37 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 ...
1
vote
1answer
26 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) ...
0
votes
5answers
83 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=...
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 ...
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)...
0
votes
1answer
29 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 ...
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?...
3
votes
0answers
43 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!
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 ...
-5
votes
0answers
40 views

Use four $4$ times, use any operations $(-+* \sqrt )$. Let the answers $21,23,25,27,29\dots $ [on hold]

Use four $4$ times, use any operations $(-+* \sqrt )$. Let the answers $21,23,25,27,29\dots $
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...
0
votes
1answer
81 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?
-1
votes
3answers
56 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
2answers
40 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$ ...
3
votes
0answers
66 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 ...
2
votes
0answers
92 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 ...
0
votes
1answer
28 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 ...
2
votes
3answers
84 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 ...
2
votes
5answers
71 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 ...
3
votes
2answers
98 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
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 ...
6
votes
2answers
107 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$ ...
2
votes
1answer
73 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 ...
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
0answers
49 views

Finding solutions in modulo

If I know $x$ modulo m and n, then under what conditions on m,n and p will i necessarily know $x$ modulo p? My initial guess is only in trivial cases, i.e. p is a multiple of m or n, but i cant seem ...
3
votes
1answer
95 views

Prove that there exist positive integers $a_1, a_2, …, a_n\ne 1$ such that $a_1a_2…\hat a_i…a_n \equiv 1 \pmod {a_i}$, for $i=1,2, …n$.

Let $n\ge 3$ be an integer. Prove that there exist positive integers $a_1, a_2, ..., a_n$ other than 1 such that $a_1a_2...\hat a_i...a_n \equiv 1 \pmod {a_i}$, for $i=1,2, ...n$. Here, $\hat a_i$ ...