Defendant Leroy Evans appeals his convictions and concurrent thirty-seven month sentences following a jury trial for the following offenses: (1) conspiracy to obtain fraudulent student visas and induce aliens to unlawfully reside in the United States, in violation of 18 U.S.C. §§ 371, 1546(a) and 8 U.S.C. § 1324(a)(l)(A)(iv), (a)(1)(B)®; (2) obtaining fraudulent student visas, in violation of 18 U.S.C. § 1546(a); and (3) inducing aliens to unlawfully reside in the United States, in violation of 8 U.S.C. § 1324(a)(l)(A)(iv), (a)(1)(B)®. After review, we affirm Evans’s convictions, vacate his sentences, and remand for resentencing.
I. BACKGROUND
A. Convictions
Because Evans’s convictions involve student visas, we review briefly the student visa process. In order for a foreign national to be admitted into the United States to attend college, the foreign national must be issued an 1-20 form from the college to which he has been admitted. He then must apply for a student visa at the United States Embassy in his home country. Once issued, the student visa is valid for the duration of the foreign national’s studies in the United States, usually lasting four to five years.
If the foreign national is already present in the United States, the foreign national, before applying for a visa, must show that he is lawfully here by presenting an 1-94 card, and then must petition the Immigration and Naturalization Service (“INS”) to change his existing status to student status by submitting a form 1-539. At the same time, the foreign national must have applied for admission to a college, and the college must approve the college admission application and issue an 1-20 form, which is signed by the school’s designated school official (“DSO”) and forwarded to the INS. The INS would then issue a student visa. If the foreign national does not enroll or withdraws from the college, the DSO notifies the INS, which then revokes the student visa.
Defendant Evans was the DSO for foreign students at Morris Brown College (“MBC”) in Atlanta from January 1998 through September 2001. Evans and his co-defendants carried out a scheme to have MBC fraudulently issue 1-20 immigration forms on behalf of undocumented aliens, or foreign nationals present in the country without 1-94 cards, which allowed the aliens to unlawfully obtain student visas from the INS even though they were not applying to or attending MBC. Co-defendants would prepare the necessary paperwork so that the 1-20 forms could be issued.
Once the fraudulent paperwork was sent to him, defendant Evans’s role was to sign the false college enrollment applications in *881his official DSO capacity and issue the I-20 forms indicating that the foreign nationals or aliens were to be students at MBC even though they were not going to be. Evans then forwarded the fraudulent forms to the INS, which issued the unlawfully obtained student visas. Evans and his co-defendants charged each foreign national between $2,500 and $5,000, which they divided among themselves, to prepare the paperwork so that a student visa would be issued to them. After examining a list of foreign nationals who had received 1-20 forms from MBC and the INS files for some of the foreign nationals on the list, the INS identified more than fifty fraudulent visa applications.
At trial, William Shepard, a professor at MBC and its legal counsel from 1999 to 2001, testified that MBC received a grand jury subpoena from the government in November 2001, requesting admission applications, financial aid applications, registration and attendance records, class schedules, transcripts, and 1-20 forms for approximately 150 foreign students. The subpoena had a return date of December 18, 2001.
Defendant Evans was responsible for assembling and providing the records. Evans indicated that he would get the documents together, but Shepard did not receive them by the December 18 deadline. Shepard then contacted the United States Attorney’s Office and was granted additional time to respond to the subpoena. Shepard still did not receive the records from Evans and requested and received a second and, later, possibly a third extension. Shepard met with defendant Evans several times, and each time Evans advised that he was working on getting the records.
On July 9, 2002, MBC received a second subpoena, which requested the same information as the first subpoena for an additional 150 foreign students and had a return date of August 20, 2002. On Shepard’s “final visit” to defendant Evans’s office, Evans provided Shepard with forty folders containing the files for two students listed on the subpoenas. Shepard observed defendant Evans print out 1-20 forms dated December 17, 2001, put them in a folder, and hand them to Shepard. Evans told Shepard that the forms had the same date because he was having problems with his computer software. On cross-examination, Shepard could not remember the date Evans provided the 1-20 forms dated December 17, 2001.
After the government rested its case, Shepard was recalled by defendant Evans and testified that he and Carolyn Jackson, who was MBC’s registrar at the time, delivered the documents to the grand jury. Shepard stated that “a significant amount of time passed” between receipt of the subpoena and delivery of the records. Specifically, Shepard testified:
I don’t recall the date that we went to the grand jury. I will say again what I have to say on this is very simple ... and that is we received the subpoena duces tecum. I attempted on a number of occasions to get the information from Mr. Evans, was unsuccessful. I even asked for an extension of time.
Eventually one night I received it about 8:00 o’clock. He printed it out and put it in folders and gave it to me, and we brought that information to the grand jury. I don’t remember the exact date it was.
Jackson testified that she, Shepard, and Evans delivered the records to the grand jury on a day when “[i]t was very cold, like it is today[, November 24, 2003].” She could not recall the specific date, other than the fact that it was cold outside at the time.
*882Following the close of evidence, the district court told the jury that “[djuring the trial of the case, there has been testimony concerning record-keeping and reporting requirements concerning students with F-1 visas. Therefore, the court finds it appropriate to give you instructions concerning these matters.” Based on 8 C.F.R. § 214.3(g), the district court specifically instructed the jury:
Federal Regulations require a school to keep records relating to each F-l student to whom it has issued a Form 1-20 while the student is attending the school and until it notifies the Immigration and Naturalization Service, the INS, that the student is not pursuing a full course of study in accordance with the reporting requirements about which I will now instruct you.
The Designated School Official must make information available to the INS upon request. The INS will periodically send each school a list of all F-l students who, according to its records, are attending that school. A Designated School Official at the school must note on the list whether or not each student on the list is pursuing a full course of study. The Designated School Official must comply with the request within 60 days of the date of the request. The school must keep a record of having complied with this reporting requirement for at least one year.
The jury convicted Evans on all counts.
After the trial, Evans filed a motion for new trial pursuant to Federal Rule of Criminal Procedure 33, arguing, among other things, that the district court erred by allowing the government to rely on Shepard’s testimony, which Evans alleged was perjurous. The district court denied the motion.
B. Sentencing
The presentence investigation report (“PSI”) assigned Evans a total offense level of twenty, consisting of (1) a base offense level of twelve, pursuant to U.S.S.G. § 2L1.1; (2) a six-level increase under U.S.S.G. § 2Ll.1(b)(2)(B), for harboring more than twenty-five but less than ninety-nine illegal aliens; and (3) a two-level upward adjustment under U.S.S.G. § 3B1.3 for abuse of a position of trust. Evans’s criminal history category of II and total offense level of twenty produced a Guidelines range of thirty-seven to forty-six months’ imprisonment. Prior to sentencing, Evans filed a motion to declare the Guidelines unconstitutional based on Blakely v. Washington, 542 U.S. 296, 124 S.Ct. 2531, 159 L.Ed.2d 403 (2004).
At sentencing on August 31, 2004, the district court denied Evans’s Blakely motion, finding that the district court was bound by the Guidelines. The district court noted that Evans had been involved in a fraud scheme in the late 1980s, though he had also been “involved in worthwhile endeavors.” The district court determined that a sentence at the low end of the Guidelines range was “fair under the circumstances,” and sentenced Evans to thirty-seven months’ imprisonment and three years’ supervised release on each count, to run concurrently. The district court did not state whether it would have imposed a different sentence under an advisory Guidelines scheme. Evans timely appealed.
II. DISCUSSION
Evans raises three issues on appeal. We address each in turn.
A. Jury Instruction Based on 8 C.F.R. § 214.3(g)
Evans argues that the district court erred by instructing the jury about *883the civil record keeping requirements set forth at 8 C.F.R. § 214.3(g). Evans contends that the district court should have specified that a violation of the reporting requirements was not criminal to prevent the jury from convicting him for violating a civil regulation. He also asserts that the district court inaccurately interpreted the regulation in the instruction and failed to properly explain the regulation to the jury.1
The § 214.3(g) regulation at issue states: An approved school must keep records containing certain specific information and documents relating to each F-l or M-l student to whom it has issued a Form I-20A or I-20M while the student is attending the school and until the school notifies the Service, in accordance with the requirements of paragraph (g)(2) of this section, that the student is not pursuing a full course of study. The school must keep a record of having complied with the reporting requirements for at least one year---- The designated school official must make the information and documents required by this paragraph available to and furnish them to any Service officer upon request.
8 C.F.R. § 214.3(g)(1).
In this case, the district court instructed the jury that the regulation required the DSO to maintain records “while the student is attending the school and until it notifies [the INS] that the student is not pursuing a full course of study in accordance with the reporting requirements.” It stated that the DSO “must make information available to the INS upon request,” and that the “school must keep a record of having complied with this reporting request for at least one year.” The instruction given by the district court accurately depicted the language of the regulation, such that it was a correct statement of law, and there was no abuse of discretion as to the phrasing. See United States v. Prather, 205 F.3d 1265, 1270 (11th Cir.2000).
This leaves the issue as to whether the instruction confused the jury. We conclude that it did not because the district court also clearly instructed the jury on the specific elements of the charged offenses, did not reference the recordkeeping requirement in connection with the charged offenses, and specified that Evans was being tried as to only the offenses set forth in the indictment. The district court also repeatedly informed the jury that it must find Evans guilty beyond a reasonable doubt. Therefore, after reviewing the jury instructions as a whole, we conclude that the jury was not misled by the § 214.3(g) instruction.2 See United States *884 v. Starke, 62 F.3d 1374, 1380 (11th Cir.1995).
B. Motion for New Trial Based on Shepard’s Testimony
Evans argues that the district court abused its discretion by denying his motion for a new trial in light of allegedly knowingly perjurous testimony elicited from Shepard by the government.3
“A conviction must be overturned which rests in part upon the knowing use of false testimony if there is any reasonable likelihood that the false testimony could have affected the judgment of the jury.” DeMarco v. United States, 928 F.2d 1074, 1077 (11th Cir.1991). However, we have refused “to impute knowledge of falsity to the prosecutor where a key government witness’ testimony is in conflict with another’s statement or testimony.” United States v. Michael, 17 F.3d 1383, 1385 (11th Cir.1994). “The fact that the witnesses’ recollections varied as to one aspect of the [case] falls far short of establishing that the government knowingly presented false testimony to the jury....” Id. Additionally, where two witnesses give conflicting or contradictory testimony, the jury is entitled to weigh them against each other to decide which is credible. See United States v. Kelley, 412 F.3d 1240, 1247 (11th Cir.2005). The credibility of witnesses is the exclusive province of the jury. Id.
A review of the record reveals that Shepard did not testify inconsistently with respect to his ability to timely comply with the subpoena. When Shepard was first questioned about whether he was able to return the subpoenaed records on time, he indicated that he was unable to comply with the subpoena within the additional time the government provided. On cross-examination, Shepard testified that he could not remember the date on which Evans gave him the 1-20 forms dated December 17, 2001. When Evans recalled Shepard, Shepard testified that “a significant amount of time passed” between receipt of the subpoena and delivery of the records and that he could not remember the exact date he delivered the records to the grand jury. Jackson also could not remember the exact date the records were delivered to the grand jury, but believed it was a cold day.
Shepard’s testimony does not necessarily conflict with Jackson’s own vague testimony regarding the date the records were delivered to the grand jury. Even if Shepard’s testimony did conflict with Jackson’s, the conflict—specifically, their recollections as to when they delivered the records—does not show that the government knowingly presented false testimony. Michael, 17 F.3d at 1385. Further, the jury, as the sole arbiter of credibility, was entitled to believe one witness over another and otherwise resolve any conflicting testimony.4 See Kelley, 412 F.3d at 1247. *885Therefore, we conclude that the district court did not abuse its discretion by denying Evans’s motion for new trial based on Shepard’s testimony.
C. Sentencing Under Booker
Evans argues that the district court committed constitutional error under United States v. Booker, 543 U.S. 220, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005), by enhancing his sentence based on facts not proven to a jury nor admitted by him. Evans was sentenced on August 31, 2004, under a mandatory Guidelines system before Booker was decided. The government concedes in its brief that the district court committed constitutional Booker error, that it cannot show beyond a reasonable doubt that the error was harmless, and that Evans is entitled to have his sentence vacated and his case remanded for resentencing. We agree.
Although we vacate Evans’s sentences, we point out that the constitutional Booker error stems not from the district court’s extra-verdict enhancements in this case, but from the use of those extra-verdict enhancements in sentencing Evans under a mandatory Guidelines scheme. Further, on appeal Evans does not contend that the district court misapplied the Guidelines in calculating his Guidelines range. Thus, on remand the district court is required to sentence Evans under an advisory Guidelines regime and shall consider the Guidelines range of thirty-seven to forty-six months and “other statutory concerns as well, see [18 U.S.C.] § 3553(a) (Supp. 2004).” Booker, 543 U.S. at 246, 125 S.Ct. at 757.5
III. CONCLUSION
For the above reasons, we affirm Evans’s convictions, vacate his sentences, and remand this case for resentencing.
AFFIRMED IN PART; VACATED AND REMANDED IN PART.