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

learn more… | top users | synonyms (1)

1
vote
1answer
182 views

Quadratic residues modulo $p$ are congruent to the even powers of $r$ modulo $p$

This is another number theory problem I've been tackling: Let $p$ be an odd prime number and let $r$ be a primitive root modulo $p$. Prove that the quadratic residues modulo $p$ are congruent to ...
3
votes
1answer
55 views

If $ p \equiv 3 \mod 4$ and $r$ primitive root, then $\mathrm{ord}_p(-r) = (p-1)/2$

I've been looking at a bunch of number theory problems lately and I need help with a few. One of them is as follows: Let $p$ be a prime number with $p \equiv 3 \mod 4$ and let $r$ be a primitive root ...
3
votes
1answer
252 views

Consecutive quadratic residues of primes that differ by 2

Show that if $p$ is prime and $p \ge 7$, then there are always two consecutive quadratic residues of $p$ that differ by 2. I think that I am supposed to use the fact that at least one of $2, 5$ and ...
0
votes
1answer
157 views

Remainder when $123456789101112\ldots$ is divided by $75$

How would you find the remainder when you divide $$1234567891011121314151617\ldots201120122013$$ (The number formed by combining the numbers from $1$ to $2013$) by $75$?
0
votes
1answer
1k views

Suppose a, b and n are positive integers. Prove that (a^n) | (b^n) if and only if a | b. [duplicate]

Suppose $a, b$ and $n$ are positive integers. Prove that $a^n\mid b^n$ if and only if $a \mid b$. I have: $$a^n\mid b^n$$ $$\implies b^n = a^n \cdot k$$ $$\implies \sqrt[n]{b^n}=\sqrt[n]{a^n}\cdot ...
0
votes
2answers
63 views

Number theory Problem .

Given that $a,b$ are positive integers find all $(a,b)$ with the following conditions : $$(a+b)\mid(\gcd(a,b))^3 $$
1
vote
3answers
59 views

If $d$ is a common divisor of $m$ and $n$, then so it is of $n$ and $m-n$

I am having trouble proving the following statement: Prove that for all integers $m$ and $n$, if $d$ is a common divisor of $m$ and $n$ (but $d$ is not necessarily the GCD) then $d$ is a common ...
5
votes
1answer
228 views

Showing $\gcd(2^m-1,2^n+1)=1$

A student of mine has been self-studying some elementary number theory. She came by my office today and asked if I had any hints on how to prove the statement If $m$ is odd then ...
11
votes
5answers
369 views

Is the value of $\sin(\frac{\pi}{n})$ expressible by radicals?

We have the followings: $\sin(\frac{\pi}{1})=\frac{\sqrt{0}}{\sqrt{1}}$ $\sin(\frac{\pi}{2})=\frac{\sqrt{1}}{\sqrt{1}}$ $\sin(\frac{\pi}{3})=\frac{\sqrt{3}}{\sqrt{4}}$ ...
1
vote
1answer
45 views

Demonstration in arithmetic function

I need help to know (in detail) how to prove that the product of two multiplicative arithmetic functions is a multiplicative arithmetic function. $$$$$f(n)$ and $g(n)$ are functions multiplicative, ...
0
votes
1answer
48 views

Help needed with an equivalence relation task on natural numbers

I'm having a bit difficulties understanding and solving this task. I would appreciate any help on how you can solve tasks like this. Here is the task: Let ~ be an equivalence relation on the ...
2
votes
3answers
130 views

For every integer $n$, the remainder when $n^4$ is divided by $8$ is either $0$ or $1$.

I am trying to prove the following statement: For every integer $n$, the remainder when $n^4$ is divided by $8$ is either $0$ or $1$. So far I have figured out that $n^4 = 8m$ or $n^4 = 8m + ...
1
vote
1answer
56 views

$(a+b\sqrt{2})^n =(c+d\sqrt{3})^m =>ab=cd=0$.

If $a,b,c,d \in Q, m,n \in N^*$ and $(a+b\sqrt{2})^n =(c+d\sqrt{3})^m$ then to show that $ab=cd=0$. An idea to solve it by contradiction but ...
2
votes
1answer
96 views

How to say this proof correctly: if $d\mid a$ and $d\mid b$ then $d\mid (a-b)$.

I believe I have this proof solved, but not sure that I wrote it correctly. Given that $d|a$ then there exist a $n$ such that $n = dk$ for some $k$ Given that $d|b$ then there exist a $m$ such that ...
2
votes
5answers
2k views

Find the four digit number?

Find a four digit number which is an exact square such that the first two digits are the same and also its last two digits are also the same.
1
vote
1answer
71 views

RSA Encryption - why does it guarantee a unique cipher?

In RSA encryption, we use $c = M^e (mod N)$ where $(e, N)$ is the public key, $M$ is the plaintext message, and $c$ is the encrypted message or ciphertext. How do we know all message $M$ (for ...
1
vote
2answers
48 views

Primitive Root question

Question: Show that if $m$ is a positive integer and $a$ is an integer relatively prime to $m$ such that $ord_{m}a = m-1$, then $m$ is prime. So if you could give me guidance and explanations of ...
0
votes
1answer
56 views

Simple pre-algebra re: GCF amd LCM

The second extra credit math problem for my god daughter (and yes she can get help). I thought I figured it out but, alas, I think not :( Here goes: Q: Positive integers a,b, and c, satisfy the ...
5
votes
5answers
281 views

Proving $n^3$ is even iff $n$ is even

I am trying to prove the following statement: Prove $n^3$ is even iff n is even. Translated into symbols we have: $n^3$ is even $\iff$ $n$ is even Since it's a double implication, I ...
0
votes
2answers
985 views

Suppose $a, b$ and $n$ are positive integers. Prove that $a^n$ divides $b^n$ if and only if $a$ divides $b$.

I think prime factorization is needed for this question: Suppose $a$, $b$ and $n$ are positive integers. Prove that $a^n$ divides $b^n$ if and only if a divides $b$.
1
vote
1answer
49 views

If $p,q$ distinct primes with $p,q \equiv 1 \bmod 4$, show that $x^2 \equiv -1 \pmod {pq}$ is solveable

I can't seem to get anywhere with this problem. Any hints would be much appreciated: Suppose that $p$ and $q$ are distinct primes satisfying $p, q \equiv 1 \bmod{4}$. Show that the congruence $x^2 ...
2
votes
3answers
218 views

Prove that there are no such positive integers $a,b,c,d$ such that $a^2 + b^2 = 3(c^2 + d^2)$

Prove that there are no positive integers a, b, c, d such that $a^2 + b^2 = 3(c^2 + d^2)$. Hint: What can you say about divisibility of a and b by 3? Look at solution with smallest possible a.
2
votes
3answers
73 views

Number invariant problem: replacing any two numbers $a$ and $b$ with $a - 1$ and $b + 3$

Numbers 1, 2, 3, ..., 2014 are written on a blackboard. Every now and then somebody picks two numbers $a$ and $b$ and replaces them by $a - 1$, $b + 3$. Is it possible that at some point all ...
-2
votes
3answers
113 views

Letting f be an arithmetic function, show that if F is multiplicative, then f is multiplicative.

I'm completely stuck on this question and don't know how to do it at all. Any help would be appreciated. Thanks.
1
vote
1answer
52 views

Elementary number theory problem for homological algebra

Hello to everybody: I'd like to know if the following statement is true or not, since if it's false it will help me solving a problem for exact sequences of modules. $``$Given $(a,b,m) \in ...
0
votes
1answer
52 views

Counting how many natural numbers satisfy a given condition.

I've defined a sequence of sequences $\{x^n\}$ as follows $x^1=(1^2,2^2,3^2,4^2,5^2,...)$ $x^2=(1,2^2,3^2,4^2,5^2,....)$ $x^3=(1,2,3^2,4^2,5^2,...)$ . . . and for each $n$ fixed, I am trying to ...
1
vote
1answer
43 views

Fixed point of multiplicative order of $2 \bmod 2n+1$

Consider the sequence (OEIS 2326) $a_n$ ($n\in\mathbb N$) such that $a_n>0$ is the least positive integer such that $$2^{a_n}\equiv 1[2n+1]$$ This is easy to prove that $$1+\log_2(n+1)\le a_n\le ...
4
votes
2answers
710 views

Prison problem: locking or unlocking every $n$th door for $ n=1,2,3,…$

I have a problem called "The Prison Problem" that I need to explain to my 9-year-old cousin. I would think that he has just started learning about divisors and perfect squares, and as such, I have a ...
2
votes
0answers
79 views

Using Graphs Changes the Solutions for Diophantine Equation? Imperfection of Graph?

Solve the Diophantine equation $$x^2+4y^2=z^2$$ The problem here is that I derived solutions using two different methods, and the both solutions do satisfy the given equation yet they are ...
0
votes
1answer
141 views

Finding the Nth element in a list of all possible numbers

This is an extension of my question found here: Given some number of digits, each with a have a specified range from 1 to some number, what would be the Nth element in the list of all permutations of ...
1
vote
1answer
63 views

Questions about $(\mathbb{Z}/2^n\mathbb{Z})^{\times}$

We have $(\mathbb{Z}/2^n\mathbb{Z})^{\times}$ is a group with $\varphi(2^n)=2^{n-1}$ elements. Prove that $x^2=1$ has exactly four solutions in $\mathbb{Z}/2^n\mathbb{Z}$. Moreover, can we show that ...
4
votes
0answers
171 views

Find all $\theta$ such that sin$\theta$ and cos$\theta$ are both rational number.

Find all $\theta$ such that sin$\theta$ and cos$\theta$ are both rational number. I thought this question might have been asked by someone else, but I couldn't find any. Currently I'm studying ...
1
vote
1answer
54 views

Finding the Nth number in a generated list

I am generating numbers as follows: Let the first digit range from 1 to 2 inclusive. Let the second digit range from 1 to 3 inclusive. Let the last digit range from 1 to 2 inclusive. I am then ...
1
vote
1answer
103 views

Elementary properties of integral binary quadratic forms

Let $f = ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$. $D = b^2 - 4ac$ is called the discriminant of $f$. We say $f$ is positive definite if $a \gt 0$ and $D \lt 0$(cf. this ...
6
votes
1answer
203 views

If all of the integers from $1$ to $99999$ are written down in a list, how many zeros will have been used?

If all of the integers from $1$ to $99999$ are written down in a list, how many zeros will have been used? I just counted how many 5 digit numbers have 1, 2, 3 or 4 zero's and subtracted all ...
1
vote
1answer
25 views

Interesting continued fraction problem $|r_i-u_0/u_1|\le\frac1{k_ik_{i+1}}$

Let $u_0/u_1$ be a rational number in lowest terms, and write $u_0/u_1=\langle a_0, a_1,...,a_n\rangle$ in standard continued fraction notation. Show that if $0\le i<n$, then ...
1
vote
1answer
53 views

Proof using the uniqueness of prime factorization

Today I saw a statement that for a,b and n are positives integers, a divides b if and only a^n divides b^n. I know if a divides b then a^n must divide b^n. But why if a^n divide b^n, then a must ...
4
votes
1answer
90 views

Triangle numbers problem

Find the smallest three-digit triangular number that can be represented both as the sum of three different triangular numbers, and as the sum of two different triangular numbers. So the ...
6
votes
2answers
446 views

What is the last non-zero digit of $50!$?

I'm looking for a fast method. I just multiplied all the numbers together modulo ten and divided by $5^{12}$ and $2^{12}$ modulo 10, which gave me $2$.
1
vote
5answers
129 views

If $n = 2 \varphi(n)$, then $n = 2^j$ for some positive integer $j$.

Let $n$ be a positive integer such that $n=2\varphi(n)$. Show that $n=2^j$ for a positive integer $j$. Basically I'm completely stumped on this question, I have no idea where to begin or what to ...
3
votes
1answer
88 views

Finding $n \in \mathbb{Z}$ such that $\sqrt{(4n-2)/(n+5)}$ is rational.

I have to find $n \in \mathbb{Z}$ such that $$\sqrt{\frac{4n-2}{n+5}}\in\mathbb{Q}.$$ I've expressed $\sqrt{\frac{4n-2}{n+5}}$ as $\sqrt{4 - \frac{22}{n+5}}$ and I think that there's no $n$ for it ...
2
votes
0answers
95 views

Need to find a better algorithm to solve a project euler problem dealing with coprime pairs.

I've been working on this for a while and found several solutions so far, but none are fast enough to find the necessary $S(10^7)$. Here is the question: For an integer $M$, we define $R(M)$ as ...
0
votes
1answer
32 views

How to calculate the rest of $2^{p^r-p^{r-1}+1}$ divided by $p^r$

I have the next problem: $p$ is an odd prime number and $r$ is a natural number, $r>1$. How can I calculate the rest of the division of $2^{p^r-p^{r-1}+1}$ by $p^r$ ?
0
votes
1answer
168 views

Multiplicative order

I tried to learn about the multiplicative order from different sources, but I want to get sure that I understand it well... As I understand, if we define to numbers, $a \in \Bbb Z$, $n \in \Bbb N^+$, ...
4
votes
1answer
166 views

Does every record of the arithmetic derivative of natural numbers occur at a practical number?

Consider the arithmetic derivative of natural numbers, as defined here. By this definition, for every integer $n>1$, with canonical prime factorization ...
10
votes
2answers
201 views

Regular $n$-gon in the plane with vertices on integers?

For which $n \geq 3$ is it possible to draw a regular $n$-gon in the plane ($\mathbb{R}^2$) such that all vertices have integer coordinates? I figured out that $n=3$ is not possible. Is $n=4$ the only ...
0
votes
1answer
176 views

Do I have this right? Are these conclusions valid in this isomorphic view of $\Bbb{R}$?

Let $F = (\Bbb{R}, \oplus_d, \cdot)$ be the field with usual $\cdot$, and $\oplus_d$ is defined as $a \oplus b = (\sqrt[d]{a} + \sqrt[d]{b})^d$. This field is isomorphic to usual $\Bbb{R}$ structure ...
0
votes
1answer
298 views

Discrete math question - Fibonacci sequence

Fibonacci sequence is embedded in Pascal’s triangle by investigating “stretched diagonals”. While this is true, it is not obvious how the sequence is embedded. Redraw Pascal’s triangle to make it ...
2
votes
1answer
92 views

Show that when $a$ is a quadratic nonresidue, $a-1$ is a quadratic residue.

Show that $$p \equiv 3\pmod 4~\land~\pmatrix{\frac{a}{p}}=-1~\rightarrow~ \pmatrix{\frac{a-1}{p}}=1$$ where p is a prime number and $\pmatrix{\frac{a}{p}}$ is a Legendre symbol. This ...
0
votes
1answer
59 views

Find the least positive residue of 2009! (mod 2011).

I am not sure how to do this. I know that 2011 is prime, and from Wilson's Theorem I know that (2010!) = -1(mod 2011). But that doesn't help much and I am not sure how you could use Euler or Fermat's ...