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

learn more… | top users | synonyms (1)

1
vote
2answers
277 views

True of false: $N = p_1p_2\cdots p_k+1$ is prime for every positive integer $k$, where $p_1,p_2,\ldots ,p_k$ are the $k$ smallest prime numbers.

We know primes are either of the form 4k+1 or 4k+3. The products of 2 numbers of the form (4k+1) or (4k+3) is of the form 4k+1 The product of 2 numbers of the form (4k+1) and (4k+3) is of the form ...
2
votes
1answer
164 views

Find the prime factor decomposition of $100!$ and determine how many zeros terminates the representation of that number.

Find the prime factor decomposition of $100!$ and determine how many zeros terminates the representation of that number. Actually, I know a way to solve this, but even if it is very large and ...
5
votes
1answer
78 views

Which sets of integers can be expressed in the form $m^2 + n^2$ and $m^2 - n^2$ where $m$ and $n$ are integers?

I'm trying to find which sets of integers can be expressed in the form $\mathrm{1})\,\,m^2 - n^2$ and, $\mathrm{2)}\,\,m^2 + n^2$ where $m$ and $n$ are integers. For the first part I expressed ...
8
votes
1answer
221 views

Algorithm to find solution to $ax^2 + by^2 = 1$ in a finite field

Let $\mathbb{F}$ be a finite field, and let $a,b \in \mathbb{F}$ be given, subject to $a\ne 0, b \ne 0$. Consider the equation $$ax^2 + by^2 = 1.$$ It is guaranteed that there exists a solution to ...
2
votes
1answer
84 views

Proof related with prime numbers and congruence

How to (dis)prove this $ (n-2)! \equiv 1 \mod n$ If n is said to be a prime number. I guess we'll have to use FERMAT’S LITTLE THEOREM, and I just don't know where to start from. Thanks in advance ...
4
votes
2answers
179 views

Proving all sufficiently large integers can be written in the form $a^2+pq$.

This is one of those numerous questions I ask myself, and to which I seem unable to answer: Can every integer greater then $657$ be written in the form $a^2+pq$, with $a\in\mathbb Z$ and $p,q$ ...
5
votes
1answer
109 views

Show that $n! \mid (p^n-1)(p^n-p) \cdots (p^n-p^{n-1})$ where $p$ is prime and $n \geq 1$.

So, I'm preparing for an exam and in one of the problems it asks us to find the number of distinct bases that we can have for an $n$ dimensional vector space over a finite field of $p$ elements ($p$ ...
1
vote
1answer
57 views

Proofs related with odd numbers and modulo 8

In my problem I have $ s! + s^{2P} \equiv 1 \mod 8$ where $s > 4, P \geq 1, s,P \in \mathbb{Z}^+$ I tried to follow that example's logic, but I could not get a result $n^2 \equiv 1 \mod 8$ ...
6
votes
2answers
201 views

If $x^3+\frac1{x^2}=1$, what is $x^3+\frac1{x^3}$?

$x^3 + \frac1{x^2} = 1$. Then, $x^3 + \frac1{x^3} = ~?$ $p + \frac1{p^2} = 47$. Then, $p + \frac1p = ~?$
0
votes
2answers
106 views

In Wilson's Theorem Why can we always split integers into mutually inverse pairs?

I mean for example $p=13$ $1*12\equiv-1 \pmod{13}$ then inverse pairs $2*7\equiv1\pmod{13}$ $3*9\equiv1\pmod{13}$ $4*10\equiv1\pmod{13}$ $5*8\equiv1\pmod{13}$ $6*11\equiv1\pmod{13}$
6
votes
1answer
150 views

Weighted sum of squares, in a finite field

Let $\mathbb{F}$ be a finite field. Let $a_1,\dots,a_n \in \mathbb{F}$ be given. I want to know whether there exists $x_1,\dots,x_n \in \mathbb{F}$ such that $$a_1 x_1^2 + a_2 x_2^2 + \dots + a_n ...
2
votes
1answer
94 views

if $n\ge4$ then there exists a prime $p$ s.t. $n=p\cdot2^{k}+a$ where $k \ge 1$, $a<2^{k}$

If $n$ is a positive integer $\ge4$ then there exists a prime $p$ such that $n=p\cdot2^{k}+a$ where $k \ge 1$, $a<2^{k}$. For example: $333 = 41\cdot2^3 + 5$ $461 = 3\cdot2^7 + 77$ ...
5
votes
3answers
774 views

$p=2^n+1$. Prove that every quadratic nonresidue modulo $p$ is a primitive root modulo $p$

This is another one of the number theory problems I've been struggling with as of late (hopefully I'm not posting too many questions at once!). Let $n$ be a positive integer and let $p=2^n+1$ be a ...
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
251 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
221 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
367 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
70 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
980 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
699 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
170 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
202 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 ...