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

learn more… | top users | synonyms (1)

6
votes
0answers
310 views

number of quadratic residues modulo n

Define $f(n)$ to be the number of quadratic residues modulo $n$. I would like to show that $f$ is multiplicative, that is, for any positive integers $m,n > 1$, $f(mn) = f(m)f(n)$ whenever $(m,n) = ...
0
votes
3answers
68 views

Is it right to say that: if $2a+1=2b$ we have a contradiction?

I am trying to prove by contradiction and I have reached the conclusion that $2a+1=2b$. Now I am tempted to say it's a contradiction and call it a night. Is it a contradiction? because one is even and ...
19
votes
10answers
2k views

How to prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?

How would I prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?
1
vote
2answers
41 views

finding large primes

I was wondering if anyone proved about a specific a number that it has to have a prime factor bigger than the currently largest known prime, without specifying how to find this factor, would it be an ...
1
vote
2answers
57 views

Chinese Remainder Theorem with coprime congruences

Suppose that $(a,m)=1$ and $(b,n)=1$, where $(x,y)$ denotes the greatest common divisor of $x$ and $y$. Show that if $$ c \equiv a \pmod{m} \\ c \equiv b \pmod{n} \\ $$ then $(c,mn)=1$. I've tried to ...
4
votes
2answers
163 views

Is it necessary to use the axiom of Regularity to prove the successor function being injective?

Basically the problem is that given an inductive set $X$ we can define the successor function on $X$ such that $S:X\longrightarrow X$ and for all $x\in X$, $S(x)=x\cup \{x\}$. So, one of Peano axioms ...
5
votes
2answers
89 views

Proof that b is not divisible by 6

$$b=\left \lfloor (\sqrt[3]{28}-3)^{-n} \right \rfloor$$ The brackets mean that the number is the largest integer smaller than $(\sqrt[3]{28}-3)^{-n} $ Proof that b is never divisible by 6. I have ...
2
votes
1answer
19 views

Showing an induction step for a congruence relation.

Let $a$ be an odd integer such that $a^{2^{n-2}}\equiv 1\; \mod {2^{n}}$. I want to show that $a^{2^{n-1}}\equiv 1\; \mod {2^{n+1}}$. My try: The integer $a^{2^{n-1}}$ is obtained from ...
4
votes
0answers
51 views

prime factorization of values of $(n+a_1)(n+a_2)\cdots(n+a_9)$

For the 9 distinct positive integers $a_1$, $a_2$, ..., $a_9$, we look at the polynomial $$p(n) = (n+a_1)(n+a_2)\cdots(n+a_9).$$ Prove that for any $a_1,a_2,\dots, a_9$, there exists a number $N$ for ...
1
vote
1answer
26 views

Question about Schnirelmann Density and Sumset: if $d(A) \ge \frac{1}{2}$ and $d(B) > 0$, wouldn't $d(A+B)=1$

I've been thinking about the Schnirelmann Density and I think that I may still be confused about SumSet and Density. It seems to me that if $d(A) \ge \frac{1}{2}$ and $d(B) > 0$, then $d(A+{B}) = ...
0
votes
4answers
112 views

How to prove that $(3+2\sqrt{2})^n=a_n+b_n\sqrt{2}$ for some positive integers $a_n,b_n$ without induction?

I have to prove that without induction: Let $n$ is non-negative integer number, prove that: $(3+2\sqrt{2})^n=a_n+b_n\sqrt{2}$ where $a_n, b_n$ are positive integer number My try: $a_1=3, b_1=2$ ...
3
votes
2answers
104 views

Find all the positive integer

Find all the positive integers (x,y), such that a) $1!+2!+3!+\cdots+ x!=y^2$ b)$1!+2!+3!+\cdots+x!=y^z$
2
votes
3answers
176 views

I need to prove that the product of two numbers equals the product of their gcd and lcm.

I cant prove it. it's just classic number theory, but it's hard. any help??
0
votes
2answers
49 views

6 is a unique number $n$ such that $n-LD(n)^2 = 2$

Let $LD(n)$ be the lowest divisor of $n$ larger than $1$. Let's find all numbers $n$ such that $n-LD(n)^2 = 2$. If $n$ is even then $LD(n) = 2$ and $LD(n)^2 = 4$. Plugging in we get $n-4=2$, so $n=6$. ...
3
votes
1answer
102 views

Schnirelmann Density: if $d(A) + d(B) \ge 1$, does it follow that $d(A+B)=1$

I am still trying to get my head around the basic properties of Schnirelmann Density. If I'm reading PlanetMath.org correctly, it states that if $d(A) + d(B) \ge 1$, then $d(A+B)=1$ Here's the exact ...
1
vote
4answers
199 views

Common factors for all palindromes

For example a palindrome of length $4$ is always divisible by $11$ because palindromes of length $4$ are in the form of: $$\overline{abba}$$ so it is equal to $$1001a+110b$$ and $1001$ and $110$ are ...
3
votes
3answers
90 views

Why does $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ have new divisors $59$ and $509$ all of a sudden?

I am a noob when it comes to math so please bear with me. Why $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ has $2$ new divisors $59$ and $509$. I mean, all of its divisors are prime factors and ...
1
vote
2answers
235 views

Find all triples of positive integers (x,y,z) such that

Find all triples of positive integers (x,y,z) such that $x^{z+1} \ - \ y^{z+1}=2^{100}$ The RHS is even, then x and y must be odd and $x^{z+1}>y^{z+1}$, but how to find out them all ?
0
votes
1answer
209 views

How to calculate such sums of Legendre symbols?

How to calculate such sums as $\sum_{x\in\mathbb{F}_p} \left(\frac{x^2+ax+b}{p} \right)$ If $x^2+ax+b$has a root, $b$ may be eliminated and the sum is evaluated to be $0+\sum_{x\in\mathbb{F}_p^*} ...
3
votes
2answers
1k views

Relationship between primitive roots and quadratic residues

I understand that if $g$ is a primitive root modulo an odd prime $p$, then Euler's Criterion tells us that $g$ cannot be a quadratic residue. My question is, does this result generalize to prime ...
2
votes
1answer
132 views

Irreducible 3rd degree polynomials over $\mathbb{Z}_3$ field?

I want to find all irreducible polynomials over $\mathbb{Z}_3$ field which have the form $x^3 + a_2 x^2 +a_1 x + a_0$. My thought process: Third degree polynomial is irreducible if it has no roots ...
0
votes
3answers
91 views

Find the digits $A,B,C$ such that $ABC+BAC+CAB=ABBC$

A,B,C are distinct digits of a three digit number such that ...
1
vote
2answers
71 views

How prove this congruence equation has four zeros solution

Question: let congruence equation $$\begin{cases} \left(\overline{a_{1}a_{2}\cdots a_{m}}\right)^2\equiv \overline{a_{m}}(\mod 10)\\ \left(\overline{a_{1}a_{2}\cdots a_{m}}\right)^2\equiv ...
4
votes
2answers
80 views

if $(m,n)=1$ is this true that $(2^m-1,2^n-1)=1$?

if $(m,n)=1$ is this true that $(2^m-1,2^n-1)=1$ ? Observing $2^i-1$'s shows that it seems true! But how to prove it? $2 \rightarrow 3$ $3 \rightarrow 7$ $4 \rightarrow 15$ $5 \rightarrow 31$ $6 ...
1
vote
1answer
106 views

Solving Diophantine equations using modular arithemtic

One common way of showing that a Diophantine equation has no solution is to show that it doesn't have solutions modulo some integer $n$. Such solutions often strike me as being very ad-hoc hence the ...
0
votes
1answer
70 views

An intermediate Modular Arithmetic exercise from AoPS

Let,$D=d_1d_2d_3d_4d_5d_6d_7d_8d_9$ be a nine-digit number consisting of the digits $d_1, . . . ,d_9$,not necessarily all distinct. Let $E=e_1e_2e_3e_4e_5e_6e_7e_8e_9$ be another nine digit number ...
2
votes
1answer
88 views

Finding the all integers solutions (x,y) [closed]

Find all integers (x,y), such that $5x^2-6xy+7y^2=383$
2
votes
1answer
98 views

Let n be a positive integer. Prove that: [duplicate]

Let n be a positive integer. Prove that: $\lfloor \sqrt{n}+\sqrt{n+1}\rfloor=\lfloor\sqrt{4n+2}\rfloor$
1
vote
1answer
81 views

Find all the natural solutions to this diophantine equation

Find all the natural solutions to this diophantine equation $968m =n^2-54257$
1
vote
1answer
112 views

negative pell's equation

If $d$ is divisible by a prime $p \equiv 3 \pmod{4}$. show that the equation $x^2-dy^2=-1$ has no solution. So far I have learn only positive Pell's equation but not negative Pell's equation. We know ...
2
votes
2answers
79 views

For how many integers $a$ is $\frac{2^{10} \cdot 3 ^8 \cdot 5^6}{a^4}$ an integer?

In Mathleague $11316$ Target #$4$, the question is: For how many integers $a$ is $$\frac{2^{10} \cdot 3 ^8 \cdot 5^6}{a^4}$$ an integer?
3
votes
3answers
156 views

Doubts about a nested exponents modulo n (homework)

As part of my homework I am supposed to find the remainder of the division of $2^{{14}^{45231}}$ by $31$. Using the ideas explained in calculating nested exponents modulo n I tried the following: ...
4
votes
2answers
72 views

How to prove that $a^{2^{n-2}} \equiv 1 \pmod{2^n}$?

Let $a$ be an odd integer and $n$ an integer such that $n\ge 3$. 1) I want to show that $a^{2^{n-2}} \equiv 1 \pmod{2^n}$ 2) Then I want to show that $(\mathbb Z/{2^n\mathbb Z})^*$, the ...
0
votes
2answers
85 views

$6^x \equiv 11 \mod{17}$

Here's a simple question using index notation. Find all incongruent solutions of the following congruence: $$6^x \equiv 11 \mod{17}.$$ Since $3$ is a primitive root modulo $17$, we have $$x ...
2
votes
3answers
74 views

How do you prove set with modulo?

Given any prime $p$. Prove that $(p-1)! \equiv -1 \pmod p$. How to prove this?
0
votes
1answer
40 views

Prove that there exist two infinite sequences that simultaneously satisfies all these conditions

Prove that there exist two infinite sequences $\langle a_n\rangle_{n\geq 1}$ and $\langle b_n\rangle_{n\geq 1}$ of positive integers such that the following conditions hold simultaneously: $$1 < ...
1
vote
0answers
74 views

Could Someone Just Verify This Proof for Me? (Euler's Theorem)

I came up with this proof for my number theory class. Is it valid? Proposition: $u\in U_m \Rightarrow u^{\varphi(m)}=1$ (Where $U_m$ is the multiplicative group of integers modulo $m$) Attempted ...
0
votes
5answers
112 views

Prove that there is no integer a for which $a^2 - 3a - 19$ is divisible by 289

Prove that there is no integer a for which $a^2 - 3a - 19$ is divisible by 289. Not got any clue. Please help.
2
votes
1answer
115 views

Solve $x^2$ $mod$ $23 = 7^2$

What is the procedure to solving $x^2$ $mod$ $23 = 7^2$? According to WolframAlpha, there is no integer solution but I am completely confused as to what steps was taken to determine that. Before ...
1
vote
3answers
48 views

Formula for Multiple of $23$

For any non-negative integer, why is $$(3^n) \cdot (2^{3n})-1$$ always a multiple of $23$? I'm thinking of pulling out the $n$ and doing something with mod.
2
votes
2answers
198 views

Find all primes $p$ such that $14$ is a quadratic residue modulo $p$.

I want to find all primes $p$ for which $14$ is a quadratic residue modulo $p$. I referred to an example that was already posted for finding all odd primes $p$ for which $15$ is a quadratic residue ...
1
vote
1answer
97 views

Primality test with polynomial congruence (preliminary to AKS algorithm)

I have trouble in understanding the proof of this primality criterion: $n$ is prime if and only if the congruence $(x+b)^n \equiv x^n+b \,\,\,\text{mod} \,n$ holds for every $b\in \mathbb{Z}$. In ...
1
vote
3answers
114 views

Sum of the digits? [closed]

Let, $\ n$ be the smallest positive number, such that: the number, $\ S=8^n5^{600}$ has 604 digits What is the sum of the digits?
29
votes
10answers
1k views

What are the applications of continued fractions?

What is the most motivating way to introduce continued fractions? Are there any real life applications of continued fractions?
3
votes
3answers
119 views

Find $a,b \in \mathbb{Z}^+$ such that : $\frac{a^{2}-2}{ab+2}\in \mathbb{Z}$

$1$. Find $a;b\in \mathbb{Z}^+$ such that : $\frac{a^{2}-2}{ab+2}\in \mathbb{Z}$ $2$. Find $m;n>1$ such that : $2^m+3^n=k^2$ $(k\in \mathbb{Z})$ Problem 1. I thought : ...
2
votes
0answers
276 views

Having trouble using the Chinese Remainder Theorem to solve a system of congruences

I'm working on a difficult assignment involving cryptography, and am nearing the end (or so I think). Summed up, I need to solve a system of congruences using the Chinese Remainder theorem. Due to ...
3
votes
2answers
64 views

Show that $n-kl$ is a perfect square

I faced a doubt in this question while solving some maths problem. Please, solve it. A natural number $n$ is chosen strictly between two consecutive perfect squares. The smaller of these two square ...
5
votes
1answer
193 views

Calculation of a square root of a big number

How can I calculate the following number: $$ \sqrt{444 \cdots (2n \text{ digits}) + 111 \cdots (n+1 \text{ digits}) - 666 \cdots (n \text{ digits})}.$$ My trying : I have tried to calculate ...
1
vote
1answer
648 views

Linear congruence proof, show congruence has exactly two incongruent solutions

Let p be an odd prime and k a positive integer. Show that the congruence $x^{2}$ $\equiv 1 \ mod p^{k}$ has exactly two incongruence solutions, namely, $x \equiv \pm 1\mod p^{k}$. I'm not sure what ...
3
votes
2answers
263 views

Totient function; if $\phi(ap)=\phi(a)\phi(p)$ and $p$ is prime, then $p\nmid a$

If p is a prime and $\phi(ap)=\phi(a)\phi(p)$ can one conclude that a and p are relatively prime? I need to show that p does not divide a, but I'm not sure if $\phi(ap)=\phi(a)\phi(p)$ is enough to ...