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

learn more… | top users | synonyms (1)

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
91 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
158 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
99 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
51 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
104 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
33 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
312 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.}\...
-1
votes
1answer
27 views

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

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
63 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 [closed]

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
66 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
80 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
86 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
28 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
2answers
182 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
88 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
138 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
273 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 ...
6
votes
2answers
118 views

Prove that $M = \mathbb Z^+$

Let $M$ be a nonempty subset of $\mathbb Z^+$ such that for every element $x$ in $M,$ the numbers $4x$ and $\lfloor \sqrt x \rfloor$ also belong to $M.$ Prove that $M = \mathbb Z^+$. Suppose $a \in ...
0
votes
0answers
56 views

What would be the output of this system given the logic?

The question is: A number arrangement machine, when given a particular input rearranges it following a particular rule. Following is an illustration: Input: 17,19,23,7,32,26,13 Step I: 24,26,30,14,...
1
vote
2answers
64 views

Legendre symbol $(-21/p)$

I am a bit confused with the question: For what prime $p$, $\left(\frac{-21}{p}\right) = 1$? I did something like that: $$\left(\frac{-21}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}...
1
vote
0answers
54 views

Is this Dirichlet series generating function of the von Mangoldt function matrix correct?

Let $\mu(n)$ be the Möbius function and let $a(n)$ be the Dirichlet inverse of the Euler totient function: $$a(n) = \sum\limits_{d|n} d \cdot \mu(d)$$ Let the matrix $T$ be defined as: $$T(n,k)=a(...
0
votes
1answer
29 views

Highest power contained in the expression.

Lets say we have a polynomial $N$ which has been expressed in $p$ where $p$ is a prime and all the coefficients in the polynomial are less than $p$. We are asked to prove, that the highest power of $p$...
2
votes
4answers
110 views

Is this possible to solve through algebra?

$$150 \equiv 17 \mod x, \qquad 100 \equiv 5 \mod x $$ Solve the simultaneous equation? Is this even a simultaneous equation? How do I find the value of $x$ too? I was doing a question and came up ...
0
votes
2answers
35 views

Module Exponential problem

Here is the problem: $ 445^{445} + 225^{225} $ mod 7 So, I know how to calculate this $445^{445}$ and this $225^{225}$ separately. But i don't know how to add them and then mod 7. In other words ...
1
vote
2answers
77 views

Numbers divisible by $11$ [duplicate]

A number is divisible by $11$, when the difference between the sum of the digits in the odd positions counting from the left (the first, third, ....) and the sum of the remaining digits is either 0 or ...