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

learn more… | top users | synonyms

0
votes
2answers
1k views

How to find modular multiplicative inverse

For example: $$63x \equiv 1 (mod 17)$$ I wanna find the multiplicative inverse here so that I can use this in the Chinese reminder theorem. Example: $$x \equiv 2 (mod 3)$$ $$x \equiv 4 (mod 5)$$ ...
0
votes
1answer
100 views

Show that if $(a, b) = 1$, $a|c$ and $b|c$, then $(a · b)|c$. [duplicate]

"Show that if $\;(a, b) = 1\;$, $\;a|c\;$ and $\;b|c$, then $(a · b)|c$." $$$$Show: We know that $$x\mid w \;\;\text{and}\;\; y\mid w \Longleftrightarrow \frac{x\cdot y}{(x,y)}\mid w$$So if$$a\mid ...
0
votes
1answer
122 views

Pascal's other triangle

Just a brainteaser question: Can you identify the generator of the following pattern of numbers?      Remark on any interesting patterns you see in the triangle.
0
votes
2answers
155 views

If $x^2+ax+b=0$ has a rational root, show that it is in fact an integer

I have tried as follows. Please help to double check the proof! Thank you! Since $x=p/q$ ($p$, $q$ are integers), $(p/q)^2+(p/q)a+b=0$ So, $(p/q)^2=-b-a(p/q)$ then, $p^2=-bq^2-a(p/q)q^2$ and, $p = ...
0
votes
3answers
353 views

The smallest positive integer in the set $\{24u+60v+200w : u,v,w \in \Bbb Z\}$is given by which of the following number?

I am stuck on the following problem: The smallest positive integer in the set $\{24u+60v+200w : u,v,w \in \Bbb Z\}$is given by which of the following number? The options are: ...
0
votes
2answers
139 views

Determining the smallest possible value

If both $11^2$ and $3^3$ are factors of the number $a \times 4^3 \times 6^2 \times 13^{11}$, then what is the smallest possible value of a? IS there any trick to answer this type question quickly? ...
0
votes
3answers
99 views

Quadratic residues, mod 5, non-residues mod p

1) If $p\equiv 1\pmod 5$, how can I prove/show that 5 is a quadratic residue mod p? 2) If $p\equiv 2\pmod 5$, how can is prove/show that 5 is a nonresidue(quadratic) mod p?
0
votes
1answer
31 views

I am stuck in this number system equation

Find the least number which when multiplied by 7 gives all 9 in the answer, how to solve this equation?
0
votes
4answers
40 views

Correlation between multiplied numbers?

I do not have a strong math background, but I'm curious as to what this pattern is from a mathematical standpoint. I was curious how many minutes there were in a day, so I said "24*6=144, add a 0, ...
0
votes
2answers
69 views

Odditiy: An Analysis of Skew-Symmetric $n\times n$ Matrices

Let $A \in M_{n×n}(\mathbb{R})$ be a skew-symmetric matrix, i.e., $A^t = −A$. Prove that if $n$ is odd, then $\det{A} = 0$.
0
votes
1answer
52 views

Question regarding Legendre symbol and Quadratic reciprocity.

How would determine the value of the following Legendre symbol is $1$ or $-1$? $$\left(\frac{\frac{p - 1}{2}}{p}\right)$$ So far, I've been able to figure out this much: $$\left(\frac{p - ...
0
votes
2answers
114 views

Is 1 bigger than 0.99999… or they are equal? [duplicate]

Here is question which always disturbs me. Could somebody help me? Is 1 bigger than 0.99999...... or they are equal? Thanks for your help.
0
votes
3answers
121 views

Positive divisors

$n$ is integer with exactly 4 different positive divisors. I need to find all possibilities for the number of prime factors of n. I know that each positive divisor of n is from the form: $d = p_1 ...
0
votes
2answers
59 views

Identity involving Möbius function

Show $\mu(n)\mu(n+1)\mu(n+2)\mu(n+3) = 0 $ if $n$ is positive integer. If $n$ is not square free, then the problem holds. If $n$ is square free, then should I consider the cases if $n$ is even and ...
0
votes
1answer
63 views

For which primes p does the series $\sum_{i=0}^\infty (\frac{10}{11})^i$ converge p-adically

For which primes p does the series $\sum_{i=0}^\infty (\frac{10}{11})^i$ converge p-adically and, when it does, to what limit?
0
votes
1answer
339 views

Legendre Symbol Sum?

I’m attempting to prove the following: If $p$ is an odd prime and $a$ is a positive integer such that $p \space \nmid \space a$ then the following expression holds: $$(\frac{a}{p}) + (\frac{2a}{p}) ...
0
votes
2answers
117 views

$ n \le \sigma(n) \le n^2$

how to prove: $$ n \le \sigma(n) \le n^2$$ $\sigma(n)$ is summation of all of positive divisors $n$
0
votes
2answers
312 views

find all positive integers solution

1.Find all positive integers solution $xy+yz+xz = xyz+2$ 2.Determine all p and q which p,q are prime number and satisfy $p^3-q^5 = (p+q)^2$ Thx for the answer 3.Find all both positive or ...
0
votes
1answer
145 views

Ratio of primes $(x^2+x+(5+6m))$ to $(x^2+x+(3+6m))$

What I did: For a large n and $x\leq n$ I counted the number of primes of the form $x^2+x+(5+6m)$ for $m = 0, 1, 2, 3,..., n/2,$ added the number of primes for each m together and called the sum A. ...
0
votes
2answers
62 views

consecutive number such that divide some square number bigger one [closed]

how to prove $\forall k\in \Bbb Z $ ,$k\ge 1$ ,there exists $k$ consecutive number such that divide some square number bigger one. it's seem we must use Chinese remainder theorem .but how?
0
votes
2answers
91 views

Find all $q\in\mathbb{Q}$ such that $ qx^2+(q+1)x+q=1 $ has integer solutions.

Find all $q\in\mathbb{Q}$ such that equation $$ qx^2+(q+1)x+q=1 $$ has integers as solutions. I tried solving it for $x$ ($q\ne0$) and stating $\sqrt{D}=\sqrt{-3q^2+6q+1}$ has to be rational, so ...
0
votes
5answers
177 views

number theory and Congruence

Can you guys help me find an example for a,b,n that let: $$a \not\equiv 0\pmod{n} $$ $$b \not\equiv 0\pmod{n} $$ But: $$ab \equiv 0\pmod{n} $$ I think I tried everything... Thank you
0
votes
1answer
76 views

Number theory The Quadratic Reciprocity

Let $p$ be an odd prime $p > 3$. What is $\dfrac{-2}{p}$? I need some help with this problem
0
votes
2answers
142 views

Number of zeros in decimal expansion

What is the number of zeros in the decimal expansion of $11^{100}-1$?
0
votes
2answers
100 views

Sylvester Theorem

Bonjour, The equation $\binom{n}{k}=m^l$ has no entire solution for l$\ge$2 and 4$\le$k$\le$n-4. Suppose that n$\ge$2k (since $\binom{n}{k}=\binom{n}{n-k}$). According to the Sylvester theorem, the ...
0
votes
3answers
154 views

Pattern in Fermat Factorization

I have the Fermat Factorizations of $n = pq$ where $p$ and $q$ are primes. I am trying to find a formula/pattern for the number of cycles required to perform the factorization in terms of $n, p, q$. ...
0
votes
1answer
96 views

Let $p \ge 5$ be a prime number. Find the largest length of an arithmetic progression satisfying the following

Let $p \ge 5$ be a prime number. Find the largest length of an arithmetic progression, of positive ratio, of positive integers whose terms do not contain the digit $1$ in their p-adic expansion.
0
votes
3answers
127 views

Given that $5n$ is a square and $75np$ is a cube, why is the smallest possible value of $n+p$ equal to $14$?

I can't solve this problem: Suppose $n$ and $p$ are integers greater than $1$, $5n$ is the square of a number, and $75np$ is the cube of a number. What is the smallest value for $n+p$? ...
0
votes
2answers
384 views

Relation between the units digit of dividend and divisor for getting the remainder

I couldn't find any online source that validated this, so I thought I would put this up here. Is it true that in order to determine the remainder of a very large number $n$ when divided with a ...
0
votes
1answer
166 views

Application of Pell's equation

Need to find $n,r$ (if any) for $121^r-2n^2=1$ where $n,r$ are natural numbers. Observed that $n$ is odd then $n=2m+1$ (say). But on replacement of $n$ by $2m+1$, increases the complexity of the ...
0
votes
4answers
371 views

For prime $p>2: 1^23^25^2\cdot\cdot\cdot(p-2)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod p$ [duplicate]

Possible Duplicate: Why is the square of all odds less than an odd prime $p$ congruent to $(-1)^{(p+1)/(2)}\pmod p$? If p is an odd prime, prove that $1^2 \times 3^2 \times 5^2 \cdots \times ...
0
votes
2answers
435 views

Convergence of $\sin(nx)$ [duplicate]

Possible Duplicate: Sine function dense in $[-1,1]$ Does there exist a subsequence $n_k$ where $1\leq k < \infty $ of the sequence of natural numbers, such that the sequence $\sin n_k$ ...
0
votes
2answers
285 views

Moving last digit to first

Is it possible to find all positive integers $n$ such that if we move its last digit to the first digit, we get $2n$? I.e $2(a_m\cdot 10^m+\ldots +a_0)=a_0\cdot 10^m+a_m\cdot 10^{m-1}\cdots+a_1$
0
votes
1answer
359 views

Accuracy of Fermat's Little Theorem?

If $a^{N-1} \neq 1\pmod{N}$ for some $a$ relatively prime to $N$, then must the equality fail for at least half the choices of $a<N$ Could someone provide proof for this statement?
0
votes
3answers
80 views

Determining the sum of a number

I'm not sure of the best way to ask this question but I will try with an example of my problem: I have three numbers, 3 and 5 ...
0
votes
1answer
97 views

A question on primitive roots

Let $p$ be an odd prime. How can Ihow that $a$ is a primitive root modulo $p$ iff $a^{(p-1)/q}\ncong 1 \pmod{p}$ for all prime divisors $q$ of $p-1$. Thanks
0
votes
2answers
312 views

From any given twelve integers, two have a difference that is a multiple of 5

How will you show that from a set of twelve given natural numbers (arbitrary) you can always find two such that their difference is divisible by $5$?
0
votes
1answer
79 views

Can every even natural number n be written as $\sum^N_{i=1}2^i\cdot f(i)$, where $f(i)$ is either zero or one?

This seems like something that should be trivial but I am having trouble showing it.
0
votes
4answers
230 views

On the solutions of $x^2+y^2=z^2$

Let $x,y,z \in \mathbb{N}$ where x is even; x,y are relatively prime and $x^{2}+y^{2}=z^{2}$. It will be tried to show that there exist $u,v \in \mathbb{N}$ relatively prime and $u> v$ and ...
0
votes
1answer
81 views

Prove if $c\geq ab$, $a|c$ and $b|c$ then $ab|c$

Prove: If $c \ge ab$ and $a|c$ and $b|c$ then $ab|c$. If $a|c$ and $b|c$ then there are integers $p$ and $q$ such that $ap=c$ and $bq=c$ All of my work has boiled down to substitutions, a lot ...
0
votes
2answers
167 views

Divisibility tests for all numbers

If $(m, 10) = 1$, choose $b$ so that $10 b \equiv 1 \pmod m$. Then $n \equiv 0 \pmod m$ if and only if $n' + ba_0 \equiv 0 \pmod m$, where $a_0$ is the unit's digit of $n$, and ...
0
votes
1answer
242 views

Number of divisors excluding set of primes S

Quite much time ago I found task where I was pleased to compute number of divisors (they are primes!) excluding numbers from set S (in other words, set S should only contain divisors of number N, ...
0
votes
4answers
315 views

Finding the last two digits of the expansion of $2^{12n}-6^{4n}$

The question is: Find the last two digits of the expansion of $2^{12n}-6^{4n}$ where $n$ is any positive integer. If we put the value of $n=1$ we would get $2800$. For $n = 2$ the result will ...
0
votes
2answers
162 views

Understanding of the proof of “$d$ solutions for $kx \equiv l \pmod{m}$”

The question is from the proof of a theorem in Hardy's An Introduction to the Theory of Numbers. THEOREM 57. If $(k, m) = d$, then the congruence $$(5.4.1)\qquad kx \equiv l \pmod{m}$$ is ...
0
votes
1answer
263 views

Sum of two squares [duplicate]

Possible Duplicate: Prove that $n$ is a sum of two squares? I was reading this and began wondering if there is a general theorem that a number of a given form is the sum of two squares. I ...
0
votes
2answers
517 views

Problems with euclidean GCD

\begin{align} 1414 &= 888 \cdot1 + 526 \qquad(1)\\ 888 &= 526 \cdot2 + 362 \qquad(2)\\ 526 &= 362 \cdot1 + 164 \qquad(3)\\ 362 &= 164 \cdot2 + 34 \,\,\,\qquad(4)\\ 164 &= 34 ...
0
votes
2answers
29 views

Can we say If q is incongruent to p modulo n then $q\equiv -p$ (mod n)

Am I right to write: If q is incongruent to p modulo n, then $q\equiv -p$ (mod n) Thanks for helping
0
votes
1answer
185 views

Why elements of the set can be Goldbach pairs for a given even number?

Let's take even number $100$ as an example (an example in the paper): Fom $2$ to $\sqrt{100}$ there's four primes:$\ 2,\ 3,\ 5,\ 7.\ $Let $$ \begin{align*} &A=\{n: n \in \mathbb{Z^+}, ...
0
votes
3answers
47 views

SAT elementary number theory

If $0 < pt < 1$, and $p$ is a negative integer, which of the following must be less than $–1$? A. $2p$ B. $2t$ I think $t<0$ so both $2p$ and $2t$ must be less than $-1$. The answer is A. ...
0
votes
1answer
144 views

If $x \ge 5 \in \mathbb Z$, then $x$ has a square mate $y$ with $y < x$.

A pair of positive integers are called square mates if their sum $x + y$ is a perfect square.(The concept of square mates is contrived just for this problem.) There's a positive square integer ...