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

learn more… | top users | synonyms (1)

2
votes
1answer
42 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?...
5
votes
1answer
83 views
+100

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
68 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
43 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
54 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
66 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
43 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
29 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
69 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 ...
1
vote
1answer
133 views
+50

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
30 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
85 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
73 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 ...
3
votes
2answers
79 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
109 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
74 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
62 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
50 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
102 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$ ...
3
votes
0answers
32 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}^...
2
votes
5answers
297 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.}\...
0
votes
1answer
25 views

Finding $A$ and $B$ using $ A \times B = \text{lcm}\,(A,B)\times\text{hcf}\,(A,B)$

The highest common factor and lowest common multiple of two numbers $A$ and $B$ are $12$ and $168$ respectively. Find the possible values of $A$ and $B$ with the exception of $12$ and $168$. I know ...
1
vote
1answer
33 views

Proof about euclidean algorithm

When calculate the gcd of a and b by using the greatest common divisor, call the remainders along the process $r_1,r_2....etc$. Show that each nonzero remainder $r_m$ with $m \geq 2$ is less than $r_{...
4
votes
2answers
62 views

Notation for “the highest power of $p$ that divides $n$”

If $p$ is a prime and $n$ an integer, is there a standard or commonly used notation for "the highest power of $p$ that divides $n$"? It's a concept that is often used repeatedly in number-theoretic ...
-2
votes
0answers
21 views

Fibonacci pseduprime in mod [on hold]

I am so afraid to look at this question as this troubling me. looking for serious help For a prime $p$, $f_n$ is Fibonacci series, can we prove $p|f_{p-1}$ and $p|f_{p+1}$ when $p = 3(mod 10)$ or ...
1
vote
3answers
50 views

Proof about property of the gcd

if $m|a$ and $m|b$ then $(a/m,b/m)=(a,b)/m$ proof show $(a/m,b/m)\leq (a,b)/m$ and $(a/m,b/m) \geq (a,b)/m$ Let $(a,b)=d$, so by bezout's identity there exists intergers x,y such that ax+by=d $$ax+...
3
votes
3answers
41 views

Smallest positive element of $ \{ax + by: x,y \in \mathbb{Z}\}$ is $\gcd(a,b)$ [duplicate]

Let $S = \{ax + by: x,y \in \mathbb{Z}\}$ and let $e > 0$ be the smallest element in $S$. Prove that $e \mid a$, and hence prove that $e = \gcd(a,b)$ I'm afraid I can't provide much of my initial ...
0
votes
1answer
65 views

Proof about GCD

Prove The GCD of more than two numbers, defined as that positive common divisor which is divisible by every common divisor, exists and can be found in the following way. Let there n numbers $a_1,a_2,.....
3
votes
2answers
39 views

proof about a lemma of divisibility

Show that if $a|b$ and $b \neq 0$ then $|a| \leq |b|$ Approach: Assume $|a| > |b|$ and $b=ak$ for some integer k $$|a| > |ak|$$ which is a contradiction becasuse $|a||k|=|ak|>|a|$ or $|ak|=...
2
votes
5answers
168 views

how to solve $2169-2^n-n^2=0$

I need to solve this equation: $2169-2^n-n^2=0$ So I have tried to guess a solution for maybe checking by derivative that it's the only one. I didn't succeeded. Thanks.
0
votes
1answer
79 views

$132$ chairs and $24$ people

There are $132$ chairs and $24$ people. The number of chairs may vary but will always be $> 24$. The chairs are numbered $(1, 2, 3, \dots, 132)$. I want to sit all $24$ people leaving a gap of ...
1
vote
0answers
26 views

Function check-up exercise

I want to make sure I did everything correctly, so here's the exercise: Given $P$ the set of positive prime numbers and be $S = \mathbb N^* - \{1\}$. $\forall n \in S,\ \pi(n)$ is the set of the ...
3
votes
1answer
52 views

Find pairs $(a,b)$ with $\gcd(a,b),\gcd(a + 1, b),\ldots, \gcd(a + k, b)$ given

Given a set of GCD's, how to find a set of numbers that satisfy all their criteria? Suppose we are given a $k$ integers $\gcd(a,b),\gcd(a + 1, b),\ldots, \gcd(a + k, b)$ for some k. How to get a and b ...
2
votes
0answers
48 views

Proof about fibonacci numbers by induction

Let $u_1,u_2,....$ be the fibonacci sequence. a) Prove by induction or otherwise thar for n>0, $$u_{n-1}+u_{n-3}+u_{n-5}+...<u_n$$ the sum on the left continuing so long as the subscript remains ...
3
votes
3answers
84 views

Problem about number representations

To multiply two numbers, such as 37 and 22, set up a table according to the following pattern. \begin{array}{|c|c|} \hline 37&22 \\ \hline 18&44 \\ \hline 9&88 \\ \hline 4&176 ...
3
votes
1answer
47 views

Relationship between decimal length and Fibonacci number

There are 6 single digit Fibonacci numbers. For all other number of digits in the decimal system, there are either 4 or 5 Fibonacci numbers. For example, between 10000 and 99999 there are 5: 10946 ...
1
vote
2answers
27 views

Proof about the quotient remainder theorem by indirect proof

Suppose that every integer can be written in the form $6k+r$ where k is an integer and r is one of the numbers 0,1,2,3,4,5. a) Show that if $p=6k+r$ is a prime different from 2 and 3, then $r=1$ or $...
0
votes
1answer
27 views

Well ordering axiom problem

Show that if a and b are positive integers, there is a positive integer n such that $na>b$. Hint: Consider the differences $b-na$, and apply the well ordering axiom. I have no approach yet. My ...
6
votes
1answer
130 views
+50

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}$...
1
vote
2answers
51 views

Finding the missing digits.

Among grandfather's papers a bill was found: $$72 \text{ turkeys \$}-67.9- $$ The first and last digit of the number that obviously represented the total price of those fowls are replaced ...
7
votes
1answer
76 views

Number of even irreducible monic polynomials of a given degree over a finite field

It is well-known that the number of irreducible monic polynomials of degree $n$ over the finite field of $q$ elements is given by the formula $$\frac{1}{n}\sum_{d\mid n}\mu\left(\frac{n}{d}\right)q^{d}...
4
votes
2answers
57 views

Show that $\sigma_0(N) = \frac{1}{N}\sum_{d|N} \sum_{l=1}^d \mathrm{gcd}(d,l)$

Here is a result I found in a textbook: $$ \sigma_0(N) = \boxed{\sum_{d|N} 1 = \frac{1}{N}\sum_{d|N} \sum_{l=1}^d \mathrm{gcd}(d,l) }$$ How does this follow from the basic results of number theory?...
7
votes
2answers
182 views

Find number of integral solutions of a*b*c*d = 600

The number of ordered solutions comes out to be 800. I need to find the number of distinct solutions but I'm stuck at calculating the possible combinations. Any ideas on how to proceed further?
4
votes
4answers
137 views

Find the highest power of $4$ in $82! + 83!$

I'am only getting $4^{13}$ as answer, but the correct answer is $40$. What am I missing?
0
votes
1answer
41 views

Prove that addition preserves order. (for natural numbers)

Prove that addition preserves order. $a ≥ b$ if and only if $a+c ≥ b+c$. (using peano axioms) I try to do it by induction on $c$. Can I use $(a+c)++ ≥ (b+c)++$. I am not sure because first we will ...
8
votes
3answers
267 views

Find the smallest positive integer which can be written as the sum of the squares of two positive integers in two different ways

Find the smallest positive integer which can be written as the sum of the squares of two positive integers in two different ways. I took extremely long to solve this I got $50= 7^2 + 1^2 $ $50= ...
2
votes
1answer
95 views

Find the number of solutions of $x^2\equiv -2\pmod{61}$

Find the number of solutions of $x^2\equiv \color{blue}{-2}\pmod{61}$ I am a bit confused If I should check Legendre symbol of $\left(\frac{\color{blue}{-2}}{61}\right)$ or Legendre symbol of $\left(...
1
vote
1answer
17 views

Function exercise check-up

I want to make sure I did everything correctly, so here's the exercise: Given $P$ the set of positive prime numbers and be $S = \mathbb N^* - \{1\}$. $\forall n \in S,\ \pi(n)$ is the set of the ...